快速排序算法是什么？

Question

如题所述

Answer 1

快速排序又称分区交换排序，是对冒泡排序的改进，快速排序采用的思想是分治思想。。

算法原理： 
(1)从待排序的n个记录中任意选取一个记录（通常选取第一个记录）为分区标准;

(2)把所有小于该排序列的记录移动到左边，把所有大于该排序码的记录移动到右边，中间放所选记录，称之为第一趟排序；

(3)然后对前后两个子序列分别重复上述过程，直到所有记录都排好序。

稳定性：不稳定排序。

时间复杂度： O（nlog2n）至O(n2)，平均时间复杂度为O（nlgn）。

最好的情况：是每趟排序结束后，每次划分使两个子文件的长度大致相等，时间复杂度为O（nlog2n）。

最坏的情况：是待排序记录已经排好序，第一趟经过n-1次比较后第一个记录保持位置不变，并得到一个n-1个元素的子记录；第二趟经过n-2次比较，将第二个记录定位在原来的位置上，并得到一个包括n-2个记录的子文件，依次类推，这样总的比较次数是： 

Cmax=∑i=1n−1(n−i)=n(n−1)/2=O(n2)

//a：待排序数组，low：最低位的下标，high：最高位的下标
void quickSort(int a[],int low, int high)
{
    if(low>=high)
    {
        return;
    }
    int left=low;
    int right=high;
    int key=a[left];    /*用数组的第一个记录作为分区元素*/
    while(left!=right){
        while(left<right&&a[right]>=key)    /*从右向左扫描，找第一个码值小于key的记录，并交换到key*/
            --right;
        a[left]=a[right];
        while(left<right&&a[left]<=key)
            ++left;
        a[right]=a[left];    /*从左向右扫描，找第一个码值大于key的记录，并交换到右边*/
    }
    a[left]=key;    /*分区元素放到正确位置*/
    quickSort(a,low,left-1);
    quickSort(a,left+1,high);
}

题目中对（41,34,53,38,26,74)排序

第一趟     26，34 ,53 ，38，41 ，74

26，34 , 41 ，38，53 ，74

26，34 , 38 ，41，53 ，74

这样序列就这样分割成了两部分，左边部分{26，34 , 38 } 均小于 基准值（41）；右边部分 {53 ，74}，均大于基准值。这样子我们就达到了分割序列的目标。在接着对子序列用同样的办法进行分割，直至子序列不超过一个元素，那么排序结束，整个序列处于有序状态。