“This is the 10th day of my participation in the August More Text Challenge. For details, see: August More Text Challenge.”

Follow me for more updates

Data structure and algorithm (I): time complexity and space complexity

Data structure and algorithm (2): stack

Data structure and algorithm (3): queue

Data structure and algorithm (4): single linked list

Data structure and algorithm (5): two-way linked list

Data structure and algorithm (6): hash table

Data Structures and algorithms (7): trees

Data Structure and algorithm (8): sorting algorithm

Data Structures and algorithms (9): classical algorithm interview questions

Selection sort

Selection is the core of choice, will be divided into the whole of the recorded for sorting sequence order and disorder, orderly area on the left, the right is disordered area, disordered area from the right to find out the location of the minimum value, and the left order district exchange, the last element in the sequence of n elements, most after sorting, n – 1 round all elements can be sorted.

Basic idea: double loop, first assume that the first element min = 0. For the first time, select the minimum value from ARR [1]~ ARR [n-1] and exchange with ARR [0]; The second time, the minimum value is selected from ARR [2]~ ARR [n-1], which is exchanged with ARR [1]. In the third time, select the minimum value from ARR [3]~ ARR [n-1] and exchange with ARR [2]; … ; At the ith, the minimum value is selected from ARR [I]~ ARr [n-1], which is exchanged with ARr [i-1]. We go through n minus 1 cycles, and we get an ordered sequence from smallest to largest.

Code logic: double loop, first assume that the first element min = 0, each round of inner loop is arr[min] and the following arR [I] comparison, if less than arr[min] min = I, after the first round of inner loop, exchange the first element and the minth element, at this time the minimum row is the most left. In the second round of the inner cycle, the first element is less than the first one. After the second round of the cycle, the second element and the minth element are exchanged. At this point, the second smallest element is already in the second place. At the end of the inner loop of the NTH round, swap the NTH element and the minth element.

Code implementation

// selectSort -(void)selectSort:(NSMutableArray*)arr{for (int I = 0; i<arr.count; i++) { int min = i; for (int j = i; j<arr.count; j++) { if ([arr[min+1] intValue] > [arr[j] intValue]) { min = j; } } NSNumber*tmp = arr[i]; arr[i] = arr[min]; arr[min] = tmp; }}Copy the code

Selection sort is faster than the unoptimized bubble sort because there are fewer exchanges.

Other sorting algorithms

Sorting algorithm :1) Direct insertion sort

Sorting algorithm :2) Hill sort

Sorting algorithm :3) Bubble sort

Sorting algorithm :4) quick sort

Sorting algorithm :5) select sorting

Sorting algorithm :6) merge sort

Sorting algorithm :7) radix sort

Sorting algorithm :8) heap sort

If you think my writing is good, please give me a thumbs-up. Your support is my biggest motivation