Sorting of arrays

• Sorting is to turn an out of order array into an ordered array through our processing
• Today we'll talk about two ways to sort an array bubble sort and select sort

Bubble sorting

• First traverse the array and compare the two next to each other. If the former is larger than the latter, change the two positions
• After traversing the array, the last number is the largest one
• Then perform the second traversal. According to the previous rules, the second largest number will run to the penultimate position
• And so on, and finally the array will be arranged in order

                 1. Let's prepare an out of order array first

var arr = [3, 1, 5, 6, 4, 9, 7, 2, 8]

                                 Next, we'll use code to sort the array

                 2. Don't worry about looping. First look at the contents of the array and change the position

// Suppose I now want to change the positions of items 0 and 1 in the array
// A third variable is required
var tmp = arr[0]
arr[0] = arr[1]
arr[1] = tmp

                 3. Traverse the array for the first time and put the largest one at the end

for (var i = 0; i < arr.length; i++) {
// Judge, if the current one in the array is larger than the latter one, then the two exchange positions
if (arr[i] > arr[i + 1]) {
var tmp = arr[i]
arr[i] = arr[i + 1]
arr[i + 1] = tmp
}
}
// After traversal, the array will become [3, 1, 5, 6, 4, 7, 2, 8, 9]

• After the first time, the last one in the array will be the largest number
• Then we execute the above code many times. The array is executed as many times as there are items

                 4. How many times to traverse according to the length of the array

for (var j = 0; j < arr.length; j++) {
for (var i = 0; i < arr.length; i++) {
// Judge, if the current one in the array is larger than the latter one, then the two exchange positions
if (arr[i] > arr[i + 1]) {
var tmp = arr[i]
arr[i] = arr[i + 1]
arr[i + 1] = tmp
}
}
}
// After that, the array is sorted

                 5. Give some optimization

• Imagine a problem, assuming that the length of the array is 9, after the eighth row
• The last eight numbers have been arranged in order, and the smallest one must be at the top
• Then the ninth time is meaningless, because the smallest one is already in the front, and there will be no change of position
• Then we don't need the ninth traversal, so we can reduce it once

for (var j = 0; j < arr.length - 1; j++) {
for (var i = 0; i < arr.length; i++) {
// Judge, if the current one in the array is larger than the latter one, then the two exchange positions
if (arr[i] > arr[i + 1]) {
var tmp = arr[i]
arr[i] = arr[i + 1]
arr[i + 1] = tmp
}
}
}

• The second question, the first time, has put the largest number at the end
• Then the second time, in fact, there is no need to compare the penultimate one with the last one
• Because we just want to put the penultimate one in the penultimate position. Even if we compare it, we won't change the position
• The third time, we have to count down the third number, so we don't have to compare it with the last two
• And so on, in fact, each time you traverse, you traverse the current number - 1 times

for (var j = 0; j < arr.length - 1; j++) {
for (var i = 0; i < arr.length - 1 - j; i++) {
// Judge, if the current one in the array is larger than the latter one, then the two exchange positions
if (arr[i] > arr[i + 1]) {
var tmp = arr[i]
arr[i] = arr[i + 1]
arr[i + 1] = tmp
}
}
}

                 6. At this point, a bubble sorting is completed

Select sort

• Let's assume that the zero in the array is the index of the smallest number
• Then traverse the array and replace the index of the previous record as long as there is a number smaller than me
• After the array traversal is completed, you can find the smallest index, and then change the smallest index to the position of 0
• Let's go through the second iteration, assuming that the first is the index of the smallest number
• After traversing the array once, find the index of the number smaller than me
• After traversal, change the position and so on, or sort the array

                 1. Prepare an array

var arr = [3, 1, 5, 6, 4, 9, 7, 2, 8]

                 2. Assume that the 0th in the array is the index of the smallest number

var minIndex = 0

                 3. Traverse the array and judge that as long as the number is smaller than me, the index of the original record will be replaced

var minIndex = 0
for (var i = 0; i < arr.length; i++) {
if (arr[i] < arr[minIndex]) {
minIndex = i
}
}
// Find the smallest index after traversal
// Exchange minIndex and 0
var tmp = arr[minIndex]
arr[minIndex] = arr[0]
arr[0] = tmp

                 4. Repeat the above code according to the length of the array

for (var j = 0; j < arr.length; j++) {
// Because the first pass assumes the 0 and the second pass assumes the 1
// So let's just assume the j-th one
var minIndex = j
// Because the smallest one has been put in the front before, the subsequent cycle does not need to judge the previous one
// Start directly from j + 1
for (var i = j + 1; i < arr.length; i++) {
if (arr[i] < arr[minIndex]) {
minIndex = i
}
}
// Find the smallest index after traversal
// The first session is to exchange with the 0, and the second session is to exchange with the 1
// Let's just exchange with the j-th one
var tmp = arr[minIndex]
arr[minIndex] = arr[j]
arr[j] = tmp
}

5. Some optimization

         As before, after the penultimate sorting, it has been arranged. The last time is not necessary

for (var j = 0; j < arr.length - 1; j++) {
var minIndex = j
for (var i = j + 1; i < arr.length; i++) {
if (arr[i] < arr[minIndex]) {
minIndex = i
}
}
var tmp = arr[minIndex]
arr[minIndex] = arr[j]
arr[j] = tmp
}

                 Before exchanging variables, you can judge if the index obtained after traversal is consistent with the current index

                 Then it proves that the current one is the smallest one, so there is no need to exchange

                 When we make a judgment, we can only exchange when the minimum citation is different from the current citation

for (var j = 0; j < arr.length - 1; j++) {
var minIndex = j
for (var i = j + 1; i < arr.length; i++) {
if (arr[i] < arr[minIndex]) {
minIndex = i
}
}
if (minIndex !== j) {
var tmp = arr[minIndex]
arr[minIndex] = arr[j]
arr[j] = tmp
}
}

                 6. At this point, the selection sorting is completed

Function parameters pass the difference between basic data types and complex data types

• As we know before, there are differences in storage between basic data types and complex data types
• Then they are also different in assignment
• Assignment between basic data types

var num = 10
var num2 = num
num2 = 200
console.log(num) // 100
console.log(num2) // 200

                 So I copied the value of num and gave it to the num2 variable exactly

                 There is no relationship between the two after assignment

         Assignment between complex data types

var obj = {
name: 'Jack'
}
var obj2 = obj
obj2.name = 'Rose'
console.log(obj.name) // Rose
console.log(obj2.name) // Rose

         Because of complex data types, variables store addresses, and real contents are stored in heap space

         Therefore, the assignment is equivalent to copying the address stored in obj to the obj2 variable

         Now, the addresses stored in obj and obj2 variables are the same, pointing to a memory space

         Therefore, if you use the obj2 variable to modify the content in the space, the space pointed to by obj will change accordingly

Parameters of function

• The parameters of the function are also assigned. When the function is called, the actual parameters assign values to the line parameters
• The rules for assigning variables are the same as before
• Function passing basic data type

function fn(n) {
n = 200
console.log(n) // 200
}
var num = 100
fn(num)
console.log(num) // 100

         As in the previous variable assignment, a copy of the value of num is copied to the row parameter n inside the function

         There is no relationship between the two

• Functions pass complex data types

function fn(o) {
o.name = 'Rose'
console.log(o.name) // Rose
}
var obj = {
name: 'Jack'
}
fn(obj)
console.log(obj.name) // Rose

         As in the previous variable assignment, copy a copy of the address stored in obj to the row parameter o inside the function

         obj outside the function and row parameter o inside the function store an address and point to a storage space

         So two variables operate on one storage space

         The data in the space is changed inside the function

         obj also sees the content after the change