快速排序技术是通过将列表分为两部分来完成的。最初,通过划分算法选择枢轴元素。枢轴的左侧部分的值小于枢轴,右侧部分的值较大。分区后,将使用相同的过程对每个单独的列表进行分区。
时间复杂度:最佳情况和平均情况为O(n log n),最坏情况为O(n ^ 2)。
空间复杂度:O(log n)
Input: The unsorted list: 90 45 22 11 22 50 Output: Array before Sorting: 90 45 22 11 22 50 Array after Sorting: 11 22 22 45 50 90
分区(数组,下,上)
输出:枢轴位于正确的位置
Begin pivot := array[lower] start := lower and end := upper while start < end do while array[start] <= pivot AND start < end do start := start +1 done while array[end] > pivot do end := end – 1 done if start < end then swap array[start] with array[end] done array[lower] := array[end] array[end] := pivot return end End
quickSort(array,left,right
输入-数据数组以及数组的上下限
输出-排序的数组
Begin if lower < right then q = partition(arraym left, right) quickSort(array, left, q-1) quickSort(array, q+1, right) End
#include<iostream> using namespace std; void swapping(int &a, int &b) { //swap the content of a and b int temp; temp = a; a = b; b = temp; } void display(int *array, int size) { for(int i = 0; i<size; i++) cout << array[i] << " "; cout << endl; } int partition(int *array, int lower, int upper) { //Hoare分区技术以找到正确的枢轴位置 int pivot, start, end; pivot = array[lower]; //first element as pivot start = lower; end = upper; while(start < end) { while(array[start] <= pivot && start<end) { start++; //start pointer moves to right } while(array[end] > pivot) { end--; //end pointer moves to left } if(start < end) { swap(array[start], array[end]); //swap smaller and bigger element } } array[lower] = array[end]; array[end] = pivot; return end; } void quickSort(int *array, int left, int right) { int q; if(left < right) { q = partition(array, left, right); quickSort(array, left, q-1); //sort left sub-array quickSort(array, q+1, right); //sort right sub-array } } int main() { int n; cout << "Enter the number of elements: "; cin >> n; int arr[n]; //create an array with given number of elements cout << "输入元素:" << endl; for(int i = 0; i<n; i++) { cin >> arr[i]; } cout << "Array before Sorting: "; display(arr, n); quickSort(arr, 0, n-1); //(n-1) for last index cout << "Array after Sorting: "; display(arr, n); }
输出结果
Enter the number of elements: 6 输入元素: 90 45 22 11 22 50 Array before Sorting: 90 45 22 11 22 50 Array after Sorting: 11 22 22 45 50 90