Bubble sort

Bubble sort is a stable sort.

code

void bubble(int *a, int n){ int tmp; for(int i = 0; i < n; i ++){ for(int j = i + 1; j < n; j ++){ if(a[i] > a[j]){ tmp = a[i]; a[i] = a[j]; a[j] = tmp; }}}}Copy the code

Optimized version

The goal of optimization is to reduce unnecessary comparisons

void bubble(int *a, int n){ int flag = 0, tmp; for(int i = 0; i < n - 1; i ++){ flag = 0; for(j = n - 1; j > i; j --){ if(a[j - 1] > a[j]){ tmp = a[j - 1]; a[j-1] = a[j]; a[j] = tmp; flag = 1; } } if(flag == 0){ return; }}}Copy the code

Quick sort

Grandma Yan thinks quicksort is an excellent internal sort

  • Best order nlog n, worst order n^2.
  • Order log n at best, order n at worst.
  • Stable sex, unstable
  • Basic thought partition thoughts: from a pivot element to sort in the table as a pivot, sort through a trip will stay sorting table into separate two parts, the left part of the elements are less than the pivot, the right half of the elements are greater than or equal to the pivot, the pivot is in place, this process is known as a quick sort. Then repeat the process recursively for each of the two sub-tables until there is only one element in each section, that is, all the elements are in the final position.

Code implementation

int partition(int *a, int low, int high){
	int pivot = a[low];
 	while(low <	 high){
    	while(low < high && a[high] >= pivot) high --;
        a[low] = a[high];
        while(low < high && a[low] < pivot) low ++;
        a[high] = a[low];
    }
 	a[low]  = pivot;
    return low;
}

void quickSort(int *a, int low, int high){
	if(low >= high) return;
	int pivot;
    pivot = partition(a, low, high);
    quickSort(a, low, pivot - 1);
    quickSort(a, pivot + 1, high);
}
Copy the code

Quickly find the KTH largest element of the array

In quicksort, after a run of sorting, the pivot element is in place. Compare the position of the pivot element pos to that of K. If pos is equal to k, then pivot is the KTH largest element. Ideally, the search efficiency of the algorithm is similar to binary search, and the time complexity of the algorithm is O(log(n)).

Code implementation

int partition(int *a, int low, int high){ int pivot = a[low]; while(low < high){ while(low < high && a[high] >= pivot) high --; a[low] = a[high]; while(low < high && a[low] < pivot) low ++; a[high] = a[low]; } a[low] = pivot; return low; } int findKTh(int *a, int low, int high, int k){ if(k > n) return -1; int pivot = partition(a, low, high); int pos = pivot + 1; if(pos == k){ return a[pivot]; }else if(pos > k){return findKTh(a, low, pivot -1, k); }else{return findKTh(a, pivot + 1, high, k); }}Copy the code