快速排序
浏览数：20 /
时间：2015年06月08日
基本思想
通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。快速排序使用分治法来把一个串（list）分为两个子串行（sub-lists）。
注意分组的时候先从右边开始比较，因为之前记录的基数是开始的位置，所以循环之前开始部分是空的，因此从右边开始。分组时需要记住左右震荡的技巧。
主要代码及示例
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
void QuickSort(int a[], int left, int right);
int main()
{
const int nLen = 20;
int a[nLen] = {0};
srand((unsigned int)time(NULL));
for (int i=0; i<nLen; i++)
{
a[i] = rand()%100;
}
/** 排序前 */
for (int i=0; i<nLen; i++)
{
printf("%2d ", a[i]);
}
printf("\n");
QuickSort(a, 0, nLen-1);
/** 排序后 */
for (int i=0; i<nLen; i++)
{
printf("%2d ", a[i]);
}
printf("\n");
}
/** 快速排序的思想
* 快速排序先选定基数（一般选择第一个），然后把大于该数的元素放到右侧，
* 小于该数的元素放到左侧，在比较的时候从右往左到从左往右式震荡式排序，
* 如此实现基数位置的排序，根据基数的正确位置，分别使用递归快排左右两
* 端，即可实现整个序列的排序
*/
int QuickPart(int a[], int left, int right)
{
int base = a[left];
while(left < right)
{
// 因为a[left]为空，所以从右边开始
while(right>left && a[right]>base)
{
right--;
}
a[left] = a[right];
while(left<right && a[left]<=base)
{
left++;
}
a[right] = a[left];
}
a[left] = base;
return left;
}
void QuickSort(int a[], int left, int right)
{
if(left < right)
{
int n = QuickPart(a, left, right);
QuickSort(a, left, n-1);
QuickSort(a, n+1, right);
}
}结果展示
47 8 13 33 22 78 11 31 53 3 1 86 37 91 62 68 25 82 61 76 1 3 8 11 13 22 25 31 33 37 47 53 61 62 68 76 78 82 86 91
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
