那些年，我们一起写过的快排

Reply Share

在几种常用的排序算法中，快速排序总体的平均效率是最优的，这里对快速排序给出C++版的代码，希望大家相互学习。

那些年，我们一起写过的快排

一、基本思路

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
快速排序是一种 不稳定 的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。

二、算法分析

实现快速排序算法的关键在于先在数组中选择一个数字，接下来把数组中的数字分为两个部分，其中，比关键字小的数字移到数组的左边，比关键字大的数字移到数组的右边。

三、相关代码实现

先看数据结构中给出的基本算法代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void QuickSort(int s[], int l, int r)  
{  
    if (l< r)  
    {        
        int i = l, j = r, x = s[l];      //以第一个数为参考基准
        while (i < j)  
        {  
            while(i < j && s[j]>= x) // 从右向左找第一个小于x的数  
                j--;   
            if(i < j)  
                s[i++] = s[j];  
            while(i < j && s[i]< x) // 从左向右找第一个大于等于x的数  
                i++;   
            if(i < j)  
                s[j--] = s[i];  
        }  
        s[i] = x;  
        QuickSort(s, l, i - 1); // 递归调用  
        QuickSort(s, i + 1, r);  
    }  
}

这里给出另一个版本的快速排序算法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
int Partition(int data[],int length,int start,int end)
{
    //定义的一个函数，在数组DATA中选择一个数字，将数组中小于关键字的
    //部分全放在关键字的左侧，大于关键字的部分放在右侧，返回关键字的索引

    //参数异常处理
    if(data==NULL || length<0 || start<0 || end>=length){
        throw new std:exception("参数输入非法!");
    }

    int index=RandomInrange(start,end);   //在start 和end 直接随机取一个值
    //data[index]作为关键字，先将其放在最后
    Swap(&data[index],&data[end]);    

    int small=start-1;
    for(index=start;index<end;++index){
     if(data[index]<data[end]){
        ++small;
        if(small!=index)
        Swap(&data[index],&data[small]);
     }
    } 

    ++small;
    Swap(&data[small],&data[end]);   //最终small的位置即对应为关键字的位置
    return small; 
}

void QuickSort(int data[],int length,int start,int end)
{
    if(start==end)
     return ;
     //将数组分成两个部分，index前面的数字都比data[index]小，后面的数字都大于或等于data[index]
      int index=Partition(data,length,start,end); 
      if(index>start)      //递归
      QuickSort(data,length,start,index-1);
      if(index<end)
      QuickSort(data,length,index+1,end);
}

四、两种算法的比较

1、这里给出的代码在选取参考数字时，使用的随机选取知道方法，而前者是直接使用第一数字作为参考；
2、后面的代码在输入参数出现异常时能正确给出响应提示，因而更加鲁棒。

1