首页 > 代码库 > 快速排序（原理和C语言实现）
快速排序（原理和C语言实现）
快速排序：
快速排序的原理：
（本文章供自己复习使用，如果有其他朋友想要了解快速排序，推荐网上一篇博客，地址附上：http://www.brieftime.net/articles/719
引自：《数据结构（C语言版）严蔚敏》
快速排序是一类藉助“交换”进行排序的方法，是对起泡排序的改进。其基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。（分而治之）
（图片来自维基百科）
我们假设要分为的两部分，左侧的数字比key值小，右侧的数字比key值大（或者等于），那么如何选择key值呢？key值的选择关系到该算法的效率，但选取一个好的key值并不简单，为了方便，我们一般选取该数组的第一个元素arr[0];
快速排序的步骤：
1.选取key值，一般选为arr[0];
2.将key值暂存（为什么要暂存，因为我们采取覆盖的方式而不是交换以提高效率）;
key=arr[0];
3. 定义两个变量（下标index）left和right，left（指向开始的元素）从左向右遍历数组，right（指向结尾的元素）从右向左遍历数组;
4.因为我们是选取的key值是arr[0]，为了方便，我们先让right遍历，因为我们要将右边的数组都变成比key值大（或等于）的数，所以遇到>=key的值就 跳过，否则就停下来交换;
值得注意的是，遍历的前提是（left<right) ，我们虽然会用一个while循环来限定该条件，但是因为我们遍历的时候会一定left和right，所以遍历的条件也要加上（left<right）
while ( left < right && arr[right] > key) { right--; } arr[left] = arr [right] (left<right是必须先满足的边界条件，然后在看是否大于key值，所以根据短路求值的特性将其放在左边)
5. 同理，left从左向右遍历;
while ( left < right && arr[left] < key ) { left++; } arr[right] = arr [left]
6.遍历完成后，就将数组分为满足条件的两个部分;
7.接下来只要再将左边分成两部分，右侧分为两部分，以此类推，直到分得的数组的长度为1,就不用再分了
附上代码：
2 {
3 if(arr_len>1){
4 int left=0,right=arr_len-1;
5 int key=arr[left];
6 while(left<right){
7 while(left<right&&arr[right]>=key){
8 right--;
9 }
10 arr[right]=arr[left];
11 while(left<right&&arr[left]<key){
12 left++;
13 }
14 arr[left]=arr[right];
15 }
16 arr[right]=key;
17 quick_sort(arr, left);
18 quick_sort(arr+right+1, arr_len-right-1);
19 }
20 }
上面的程序也可以改写每次都与key值交换，但这样效率会降低;
也可以利用快慢指针的思想实现快排，并且用循环右移的方式使其具有稳定性
2 {
3 if(arr_len>1){
4 int i,j;
5 int k;
6 int temp;
7 for(i=0,j=1;j<arr_len;j++){
8 //只移动比key值小的
9 if(arr[j]<arr[0]）{
10 temp=arr[j];
11 //循环右移i+1到j的数（不移动i所指的数)
12 for(k=j-1;k>i;k--){
13 arr[k+1]=arr[k];
14 }
15 arr[i+1]=temp;
16 i++:
17 }
18 }
19 temp=arr[0];
20 //交换key值和当前i所指的值;
21 arr[0]=arr[i];
22 arr[i]=temp;
23 quick_sort(arr, i);
24 quick_sort(arr+i+1, arr_len-i-1);
25 }
26 }
（如果有错误的地方，还请帮忙指出）……
快速排序（原理和C语言实现）