首页 > 代码库 > 排序-快速排序算法

排序-快速排序算法

快速排序算法是冒泡排序的一种改进,先找到一个元素,设置2各游标,i从前到后遍历,j从后向前遍历,如果第j个小于此元素,则调换,然后i++,如果遇到第i个大于此元素,则调换。其实这就是一个挖坑-填坑的过程。具体的代码如下:

int base_quicksort(int A[], int first, int last){    int temp = A[0];    int i = 0;    int j = sizeof(A[])/4 - 1;
while(i != j){ while(A[j] > temp) j--; A[i] = A[j]; while(A[i+1] < temp) i++; A[j] = A[i+1]; A[j] = temp; return j; }}void quicksort(int A[], int first, int last){ if(first < last){ int i = base_quicksort(A, first, last); quicksort(A, first, i-1); quicksort(A, i+1, last); } }

 快速排序算法的时间复杂度为:平均情况下是O(nlog2n),最坏情况:O(n2)

空间复杂度为O(log2n)

不稳定,较复杂。

排序-快速排序算法