继shell发明了shell排序过后呢，各位计算机界的大牛们又開始不爽了，为什么他能发明。我就不能发明呢。于是又有个哥们蹦出来了。哎。。。那么多排序，就木有一个排序是中国人发明的。顺便吐槽一下，一百年的天朝的历史书里还在吹，祖冲之第一个发现圆周率，率先世界一千多年......
高速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。
步骤为：
1，从数列中挑出一个元素，称为 "基准"，
2。又一次排序数列。全部元素比基准值小的摆放在基准前面，全部元素比基准值大的摆在基准的后面（同样的数能够到任一边）。
在这个分区退出之后。该基准就处于数列的中间位置。这个称为分区操作。
3，递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。
4，递归的最底部情形，是数列的大小是零或一。也就是永远都已经被排序好了。
尽管一直递归下去，可是这个算法总会退出，由于在每次的迭代中，它至少会把一个元素摆到它最后的位置去。
①先假定序列的第一个元素为标志位，从第一位到最后一直与标志位进行比較。比标志位小的所有移到标志位的左边。比标志位大的所有移到标志位的右边
②对标志位左边的进行步骤①操作。右边亦是。形成新的两个标志位，依次递归下去
源码：
#include "stdafx.h"
#include <stdlib.h> void swap(int arr[],int i, int j) //交换
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
} int getPoint(int arr[],int low ,int high)
{
int res = arr[low]; //第一次假定第一个元素即为标志点
while (low < high)
{
while ((low < high) && (arr[high] >= res))
{
high--;
}
swap(arr,low,high); while ((low < high) && (arr[low] <= res))
{
low++;
}
swap(arr,low,high);
} return low;
} void QSort(int arr[],int low ,int high)
{
if (low < high)
{
int lowIndex = getPoint(arr, low, high); QSort(arr, low,lowIndex-1);
QSort(arr, lowIndex+1,high);
}
} void Quick_Sort(int arr[], int low, int high)
{
QSort(arr, low, high-1);
} int main(void)
{
int arr[10]; for ( int i=0; i<10; i++) //初始化数据
{
arr[i] = rand()%33; //随机生成数据
}
printf("Before sort:\n"); //打印排序前的数据
for (int i = 0; i < 10; i++)
{
printf("%d ",arr[i]);
} //開始排序
Quick_Sort(arr,0,10); printf("\nAfter sort:\n"); //打印排序后的数据
for (int i = 0; i < 10; i++)
{
printf("%d ",arr[i]);
}
system("pause");
return 0;
}
执行结果：
Before sort:
8 20 31 1 29 16 27 21 1 11
After sort:
1 1 8 11 16 20 21 27 29 31 请按随意键继续. . .
如有错误，望不吝指出。