Original link: https://www.bytecho.net/archives/2075.html
Recently, I have been studying data structures in an all-round way, and commonly used algorithms are recorded: Quick sort, a kind of exchange sort, is an improvement on bubble sort and an unstable sort.
Average time complexity: $O(nlogn)$
Worst time complexity (degenerate to bubble sort): $O(n^2)$
#include <iostream> using namespace std; //快速排序void quickSort(int arr[], int low, int high); void quickSort_another(int *arr, int left, int right); int partition(int arr[], int low, int high); int main() { int arr[] = {5, 2, 4, 6, 1, 3}; quickSort(arr, 0, 5); for(auto cur:arr) cout << cur << " "; cout << endl; quickSort_another(arr, 0, 5); for(auto cur:arr) cout << cur << " "; return 0; } int partition(int arr[], int low, int high) { int pivot = arr[low]; //第一个元素作为基准while(low < high) //low == high时结束{ while(low < high && arr[high] >= pivot) --high; arr[low] = arr[high]; //此时arr[high]小于基准元素while (low < high && arr[low] <= pivot) ++low; arr[high] = arr[low]; //此时arr[low]大于基准元素} arr[low] = pivot; //此时low == high return low; //返回基准元素的下标} void quickSort(int arr[], int low, int high) { if(low < high) { int pivot_pos = partition(arr, low, high); quickSort(arr, low, pivot_pos - 1); //对基准元素左边的数组进行快速排序quickSort(arr, pivot_pos + 1, high); //对基准元素右边的数组进行快速排序} } //写法二void quickSort_another(int *arr, int left, int right) { if (left >= right) return; int pivot = arr[left]; int i = left + 1, j = right; while (i <= j) { while (i <= right && arr[i] < pivot) i++; while (j >= left && arr[j] > pivot) j--; if (i <= j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; i++; j--; } } arr[left] = arr[j]; arr[j] = pivot; quickSort_another(arr, left, j - 1); quickSort_another(arr, j + 1, right); }
This article is reproduced from: https://www.bytecho.net/archives/2075.html
This site is for inclusion only, and the copyright belongs to the original author.