首页 > 代码库 > 排序算法：快速排序法
排序算法：快速排序法
快速排序是找出一个元素（理论上可以随便找一个）作为基准(pivot),然后对数组进行分区操作,使基准左边元素的值都小于或等于基准值, 基准右边的元素值 都大于基准值。然后以基准数为界，分左和右两个子序列，递归调用，直至完成排序。
该方法的基本思想：一个未排序数组s[]
1．先从数列中取出一个数作为基准数（一般取第一个），保存到temp=s[l]，此时第一个数组形成一个“坑”；
2．分区过程, i = l 和 j = r
(1)此时s[i]形成一个“坑”，从j向前遍历，直至找到一个s[j]<temp，则s[i]=s[j]，i++；
(2)此时s[j]形成一个“坑”，从i向后遍历，直至找到一个s[i]>temp，则s[j]=s[i]，j--；
(3)当j==i直接停止循环；
3．再对左右区间重复第二步，直到各区间只有一个数；
原始数据：初始值l = 0（基准数下标） r = 7(最大下标) temp = s[i] = 6（基准数值）
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 6 | 10 | 4 | 90 | 52 | 77 | 8 | 3 |
第一次循环过程：
| 0 |
| 6 |
基准数：temp=s[0]=6
1,初始 i=l=0, j=r=7, 由j向后查找; 由于temp>s[7]，则s[0]=s[7]=6, (i++)-->1, j=7;
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 3 | 10 | 4 | 90 | 52 | 77 | 8 | 3 |
2,i=1, j=7, 由i向前查找; 由于temp<s[1], 则s[7]=s[i]=10, (j--)-->6, i=1;
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 3 | 10 | 4 | 90 | 52 | 77 | 8 | 10 |
3,i=1, j=6, 由j向后查找; 由于temp>s[2], 则s[1]=s[2]=4, (i++)-->2, j=2; 由于j==i, 停止循环, s[i]=temp;
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 3 | 4 | 6 | 90 | 52 | 77 | 8 | 10 |
第一次结束后，从6将数组分成左右两个子数组，进行递归；
代码如下：
/************************************************************************************** * Description: * Input Args: * Output Args: * Return Value: *************************************************************************************/int quick_sort (int s[], int l, int r){ if(l < r) { int i = l, j = r, temp = s[l]; while (i < j) { while(i < j && s[j] >= temp) //小到大 j--; if(i < j) s[i++] = s[j]; while(i < j && s[i] < temp) i++; if(i < j) s[j--] = s[i]; } s[i] = temp; quick_sort(s, l, i - 1); //左子数组 quick_sort(s, i + 1, r); //右子数组 } return 0;} /* ----- End of quick_sort() ----- */
参考链接：http://blog.csdn.net/morewindows/article/details/6684558
排序算法：快速排序法