快速排序 - 算法

快速排序是对冒泡法排序的一种改进。

快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高，因此经常被采用，再加上快速排序思想—-分治法也确实实用，因此很多软件公司的笔试面试，包括像腾讯，微软等知名IT公司都喜欢考这个，还有大大小的程序方面的考试如软考，考研中也常常出现快速排序的身影。

该方法的基本思想是：
1．先从数列中取出一个数作为基准数。
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3．再对左右区间重复第二步，直到各区间只有一个数。

算法过程参考：
http://www.cnblogs.com/morewindows/archive/2011/08/13/2137415.html

以对n个无序数列A[0], A[1]…, A[n-1]采用快速排序方法进行升序排列为例进行讲解。

(1)定义两个变量low和high，将low、high分别设置为要进行排序的序列的起始元素和最后一个元素的下标。第一次，low和high的取值分别为0和n-1，接下来的每次取值由划分得到的序列起始元素和最后一个元素的下标来决定。

(2)定义一个变量key，接下来以key的取值为基准将数组A划分为左右两个部分，通常，key值为要进行排序序列的第一个元素值。第一次的取值为A[0]，以后毎次取值由要划分序列的起始元素决定。

(3)从high所指向的数组元素开始向左扫描，扫描的同时将下标为high的数组元素依次与划分基准值key进行比较操作，直到high不大于low或找到第一个小于基准值key的数组元素，然后将该值赋值给low所指向的数组元素，同时将low右移一个位置。

(4)如果low依然小于high，那么由low所指向的数组元素开始向右扫描，扫描的同时将下标为low的数组元素值依次与划分的基准值key进行比较操作，直到low不小于high或找到第一个大于基准值key的数组元素，然后将该值赋给high所指向的数组元素，同时将high左移一个位置。

(5)重复步骤(3) (4)，直到low的植不小于high为止，这时成功划分后得到的左右两部分分别为A[low……pos-1]和A[pos+1……high]，其中，pos下标所对应的数组元素的值就是进行划分的基准值key，所以在划分结束时还要将下标为pos的数组元素赋值为 key。

(6)将划分得到的左右两部分A[low……pos-1]和A[pos+1……high]继续采用以上操作步骤进行划分，直到得到有序序列为止。

//代码：
#include <stdio.h>

//快速排序 
void quick_sort(int s[], int l, int r)   // l为left左侧， r为right右侧 
{  
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;  
        quick_sort(s, l, i - 1);  // 分治 左侧 
        quick_sort(s, i + 1, r);  // 分治 右侧
    }  
}  

int main()
{
int i;
int arr[] = {10,5,30,9,40,21,31};
for(i = 0; i < 7; i++)
    {
printf("%3d",arr[i]);
    }
printf("\n");

    quick_sort(arr,1,3);

for(i = 0; i < 7; i++)
    {
printf("%3d",arr[i]);
    }
printf("\n");
return 0;
}

秒客网

快速排序 - 算法

相关文章