首页 > 代码库 > 快速排序(quicksort)

快速排序(quicksort)

        快速排序是对冒泡排序算法的一种改进型算法,而且快速排序也采用了分治法的思想。快速排序是不稳定排序,

平均时间复杂度为:O(n*logn),最坏时间复杂度为:O(n*n),空间时间复杂度:O(logn),但快速排序通常是用于排

序的最佳实用的选择。

 

快速排序的思想:从数组选取一个数(通常是第一个数)作为标准,从数组的高位开始查找,找到比作为标准数小的数

,然后进行交换,又从数组的低位开始查找,找到比作为标准大的数,然后进行交换,重复以上步骤,直至从高位到低位,

低位到高位重合为止。

 

示例:

                     6    3    8    7     2

第一次交换:2     3    8     7     6

第二次交换:2     3    6      7    8

第一遍排序完成,第二三就不详细说了。

 

示例代码:

 

#include <stdio.h>int Qsort(int array[], int low, int high)     //进行排序{    int mark = array[low];    while(low<high)         //判断是否重合    {        while(low<high && array[high]>=mark)    //从高位到低位查找小的数            high--;        array[low] = array[high];        while(low<high && array[low]<=mark)     //从低位到高位查找大的数            low++;        array[high] = array[low];    }    array[low] = mark;    //将标记的数放到合适的位置    return low;}void QuickSort(int array[], int low, int high)    //进行分解,采用分治法{    if(low<high)    {        int k = Qsort(array, low, high);        QuickSort(array, low, k-1);        QuickSort(array, k+1, high);    }}int main(){    int n;    int array[100];    printf("请输入数组的大小:");    scanf("%d", &n);    printf("请输入数组中的各个数:");    for(int i = 0; i<n; i++)        scanf("%d", &array[i]);    QuickSort(array, 0, n-1);    for(int i = 0; i<n; i++)        printf("%d  ", array[i]);    return 0;}