“This is the ninth 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

Quick sort

In essence, quicksort is a recursive divide and conquer on top of bubble sort. It’s an optimization of bubble sort, and they’re all part of swap sort, and the core of swap sort is swap

Basic idea: the sequence to be sorted is divided into two independent parts by the hub value as the boundary, the elements on the left of the hub value are smaller than the elements on the right, and then the two parts of the data are quickly sorted by this method, the whole sorting process can be recursive, in order to achieve the whole data into an ordered sequence. In the process of quicksort, each cycle selects an element as the hub value, which is used to divide the sequence into two parts. There are many ways to select the hub value. Here, we adopt the three-number median method, that is, to sort the first, middle and last three elements, and take the middle value as the hub value

Code idea: first use the three numbers to take the middle method, find out the hub value, the head in the tail of the three positions of the number to compare, the maximum value in the tail position, the minimum value in the head position, the hub value and the right number of the second position of the value exchange, this time the hub value on the right number of the second position. Then the left pointer starts from the first position on the left and goes to the right, and stops when it encounters something larger than the hub value. The right pointer starts from the left position of the hub value and goes to the left, and stops when it encounters something smaller than the hub value, and then determines that the two Pointers do not meetleft<rightAfter the swap, the two Pointers continue to loop until the two Pointers meetleft=rightIn this case, all elements to the left of the left position are smaller than the elements to the right, and then the hub value is inserted into the left position, so that all values to the left of the hub value are smaller than the values to the right

// quicksort -(void)quitSort:(NSMutableArray*)arr{[self recusiveQuit:arr left:0 right:(int)arr.count-1]; } -(void)recusiveQuit:(NSMutableArray*)arr left:(int)left right:(int)right{if (left>=right) {return; } int pivot = [self selectPivot:arr left:left right:right]; Int I = left; // int I = left; // int I = left; ++ I int j = right-1; While ([arr[++ I] intValue] < pivot) {} while ([arr[++ I] intValue] < pivot) {} while ([arr[++ I] intValue] < pivot) {} while ([arr[++ I] intValue] < pivot) ([arr[--j] intValue] > pivot) {} if (I <j) {self swapArray:arr index1: I index2:j]; }} // Put the hub in the right place [self swapArray:arr index1: I index2:right-1]; [self recusiveQuit:arr left:left right:i-1]; [self recusiveQuit:arr left: I +1 right:right]; } -(int)selectPivot:(NSMutableArray*)arr left:(int)left right:(int)right{ int center = (left+right)/2; if ([arr[left] intValue] > [arr[center] intValue]){ [self swapArray:arr index1:left index2:center]; } if ([arr[center] intValue] > [arr[right] intValue]){ [self swapArray:arr index1:center index2:right]; } if ([arr[left] intValue] > [arr[center] intValue]){ [self swapArray:arr index1:left index2:center]; } [self swapArray:arr index1:center index2:right-1]; return [arr[right-1] intValue]; // Return the hub value}Copy the code

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