排序与查找
1.选择排序
算法：N元数组a[0]~a[N-1]由小到大排序：
第0步:找到a[0]~a[N-1]中的最小值元素与a[0]交换;
第1步:找到a[1]~a[N-1]中的最小值元素与a[1]交换；
第2步:找到a[2]~a[N-1]中的最小值元素与a[2]交换；
…
第i步:找到a[i]~a[N-1]中的最小值元素与a[i]交换;
…
第N-2步:找到a[N-2]~a[N-1]中的最小值元素与a[N-2]交换。
算法停止。
思考：由大到小排序算法如何改动？
#include "stdio.h"
#define N 10
void SelSort(int a[N]) { /*选择排序函数*/
int i,j,minj,t;
for (i = 0;i < N-1;i++) {
for (j = i + 1;j < N;j++)
if(a[j] < a[i]) {
t = a[i];
a[i] = a[minj];
a[minj] = t;
}
}
}
这样中间有些交换是没有必要的，设定一个minj变量记录当前一趟最小值的下标。可以减少变量交换的次数。改进如下：
void SelSort(int a[N]) { /*改进选择排序函数*/
int i,j,minj,t;
for (i = 0;i < N-1;i++) {
minj = i;
for (j = i + 1;j < N;j++)
if(a[j] < a[minj])
minj = j;
if(minj != i) {
t = a[i];
a[i] = a[minj];
a[minj] = t;
}
}
}
void main(){
int a[N],i;
for(i = 0;i < N;i++)
scanf("%d",a + i);
SelSort(a);
for (i = 0;i < N;i++)
printf("%6d",a[i]);
}
2.插入排序
引例：写一个函数，将一个整型数x插入到由小到大排列的整型数组a[0]~a[N-1]中，使得插入元素后的数组a[0]~a[N]保持升序。
void insert(int a[N+1],int x) {
int i = N - 1;
while (i >= 0 && a[i] > x) {
a[i+1] = a[i];
i--;
}
a[i+1] = x;
}
算法要点：将升序数组中大于x的所有元素向后挪动一个下标位置；循环退出时，下标i＋1位置为一空位置，正好是正确插入元素x的位置.
插入排序算法：
N元数组a[0]~a[N-1]由小到大排序：
第1步:将a[1]插入a[0]~a[1]中，使得a[0]~a[1]升序;
第2步:将a[2]插入a[0]~a[2]中，使得a[0]~a[2]升序；
第3步:将a[3]插入a[0]~a[3]中，使得a[0]~a[3]升序；
…
第i步:将a[i]插入a[0]~a[i]中，使得a[0]~a[i]升序；
…
第N-1步:将a[N-1]插入a[0]~a[N-1]中，使得a[0]~a[N-1]升序；
算法停止。
思考：由大到小排序算法如何改动？
#include "stdio.h"
#define N 10
void InsSort(int a[N]) { /*N元数组插入排序*/
int i,j,x;
for(i = 1;i < N;i++){
x = a[i];
j = i - 1;
while(j >= 0 && a[j] > x) {
a[j+1] = a[j];
j--;
}
a[j+1] = x;
}
}
void main() {
int a[N],i;
for (i = 0;i < N;i++)
scanf("%d",&a[i]);
InsSort(a);
for (i = 0;i < N;i++)
printf("%6d",a[i]);
}
3.冒泡排序
相邻元素比较大小发生交换使最大值(最小值)"浮出"到数组尽头：
(1)若a0>a1,则a0?a1;(使a1为a0,a1的大者)
(2)若a1>a2,则a1?a2;(使a2为a1,a2的大者)
…
(i) 若ai-1>ai,则ai-1?ai交换(使ai为ai-1,ai的大者)
按照这种方法运算下去，数组中的最大元一定可以移动到最后一个下标位置! 冒泡排序算法：
N元数组a[0]~a[N-1]由小到大排序：
第1步:找到a[0]~a[N-1]中的最大元浮动到a[N-1];
第2步:找到a[0]~a[N-2]中的最大元浮动到a[N-2]；
第3步:找到a[0]~a[N-3]中的最大元浮动到a[N-3]；
…
第i步:找到a[0]~a[N-i]中的最大元浮动到a[N-i];
…
第N-1步:找到a[0]~a[1]中的最大元浮动到a[1]。
算法停止.
思考：由大到小排序算法如何改动？
#include "stdio.h"
#define N 10
void main() {
int a[N],i,j,t;
printf("Input %d int numbers:\n",N);
for (i = 0;i < N;i++)
scanf("%d",a+i);
for (i = 1;i < N;i++)
for (j = 0;j < N-i;j++)
if (a[j] > a[j+1]) {
t = a[j];
a[j] = a[j+1];
a[j+1] = t;
}
printf("Reslut:");
for(i = 0;i < N;i++)
printf("%6d",a[i]);
printf("\n");
}
冒泡排序的改进：
显然，当数组已经排好序时，不会发生元素的浮动(即元素的交换值),因此，可设一个标变量，当内循环未发生前后两元素交换值时,就跳出外循环。
void BubSort(int a[N]) {
int i,j,t;
int sorted;
for (i = 1;i < N;i++) {
sorted = 1;
for(j = 0;j < N-i;j++)
if (a[j] > a[j+1]) {
t = a[j];
a[j] = a[j+1];
a[j+1] = t;
sorted = 0;
}
if(sorted) break;
}
}
4.索引排序
目的：待排序数组保持不变，而元素的顺序通过下标数组中的下标顺序来体现。
#include "stdio.h"
#define N 10
void InxBubSort(int a[N],int p[N]) {
/*p[N]为下标数组,也称为索引数组*/
int i,j,k;
for (i = 0;i < N;i++)
p[i] = i;
for (i = 1;i < N;i++)
for (j = 0;j < N-i;j++)
if (a[p[j]] > a[p[j+1]]) {
k = p[j];
p[j] = p[j+1];
p[j+1] = k;
}
}
void main() {
int a[N],p[N],i;
printf("Input %d int number:\n",N);
for (i = 0;i < N;i++)
scanf("%d",&a[i]);
InxBubSort(a,p);
printf("Result:\n");
for(i = 0;i < N;i++)
printf("%6d",a[p[i]]);
printf("\n");
}
对分查找(也称为折半查找或拆半查找)
算法：
设a[0]~a[N-1]已升序，待查找元素为x
令起点下标 h=0; 终点下标 r=N-1;
中点下标 m=(h+r)/2;
@当h<=r时执行以下步骤：
若x==a[m]则表明查找成功，a[m]为所找元素；
x<a[m],显然x在a[h]~a[m-1]之间，则
h不变;r=m-1;m=(h+r)/2;转@
x>a[m],显然x在a[m+1]~a[r]之间，则
r不变;h=m+1;m=(h+r)/2;转@
若h>r，则表明查找失败.
该算法仅适用于在已排序的数组中快速查找所需要的元素,具有效率高的突出优点。可以证明，当数组长度为n个元素时，该算法的平均比较次数不会超过log2n+1。
/*升序数组a[N]中查找x,找到返回有效下标0~N-1, 查找失败返回-1*/
int Locate(int a[N],int x) {
int h,r,m;
h = 0;
r = N-1;
m = (h + r) / 2;
while (h <= r && x != a[m])
if (x < a[m]) {
r = m - 1;
m = ( h + r ) / 2;
} else {
h = m + 1;
m = ( h + r ) / 2;
}
if (h > r)
return –1;
return m;
}
研究思考：怎样用对分查找实现如下查找要求：
在N元升序数组a[0]~a[N-1]中查找元素a[i],使得a[i]满足: 元素a[0]~a[i-1]均小于或等于x且
a[i]~a[N-1]均大于x。
第二篇：C语言简单查找排序方法及代码
第一部分 查找
1、线性查找法：
import java.util.Scanner;
public class SearchDataElement {
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
int[]array;
array=new int[]{8,7,5,4,1,5,9,6,3,4};
for(int i=0;i<array.length;i++)
System.out.println(""+array[i]);
System.out.println();
int replay=0;
do{
System.out.print("请输入要查找的数字0-10");
int num=scanner.nextInt();
lable:{
for(int t=0;t<array.length;t++)
{if(num==array[t])
{
System.out.println("array["+t+"]="+array[t]);
break lable;
}
}
System.out.println("输入的数字数组中不存在");
}
System.out.println("重新查找1:继续 0:结束?");
replay=scanner.nextInt();
}while(replay==1);
}
}
2、二分查找算法
import java.util.Scanner;
public class SearchBinary {
public static int searchB(int[]arr,int key)
{int low=0;
int high=arr.length-1;//
while(high>=low)
{
int mid=(low+high)/2;
if(key<arr[mid])
high=mid-1;
else if(key==arr[mid])
return mid;
else
low=mid+1;
}
return-1;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[]array=new int[]{2,4,7,11,14,25,33,42,55,64,75,88,89,90,92};
int key;
Scanner scanner=new Scanner(System.in);
System.out.println("\n 请输入关键字:");
key=scanner.nextInt();
//
int result=searchB(array,key);
if(result!=-1)
System.out.printf("\n%d found in arrray element %d\n", key,result);
else
System.out.printf("\n %d not found in array\n",key);
}
}
C语言排序方法
学的排序算法有：插入排序，合并排序，冒泡排序，选择排序，希尔排序，堆排序，快速排序，计数排序，基数排序，桶排序（没有实现）。比较一下学习后的心得。
我不是很清楚他们的时间复杂度，也真的不知道他们到底谁快谁慢，因为书上的推导我确实只是小小了解，并没有消化。也没有完全理解他们的精髓，所以又什么错误的还需要高手指点。呵呵。
1.普及一下排序稳定，所谓排序稳定就是指：如果两个数相同，对他们进行的排序结果为他们的相对顺序不变。例如A={1,2,1,2,1}这里排序之后是A = {1,1,1,2,2} 稳定就是排序后第一个1就是排序前的第一个1，第二个1就是排序前第二个1，第三个1就是排序前的第三个1。同理2也是一样。这里用颜色标明了。不稳定呢就是他们的顺序不应和开始顺序一致。也就是可能会是A={1,1,1,2,2}这样的结果。
2.普及一下原地排序：原地排序就是指不申请多余的空间来进行的排序，就是在原来的排序数据中比较和交换的排序。例如快速排序，堆排序等都是原地排序，合并排序，计数排序等不是原地排序。
3.感觉谁最好，在我的印象中快速排序是最好的，时间复杂度：n*log(n)，不稳定排序。原地排序。他的名字很棒，快速嘛。当然快了。我觉得他的思想很不错，分治，而且还是原地排序，省去和很多的空间浪费。速度也是很快的，n*log(n)。但是有一个软肋就是如果已经是排好的情况下时间复杂度就是n*n,不过在加入随机的情况下这种情况也得以好转，而且他可以做任意的比较，只要你能给出两个元素的大小关系就可以了。适用范围广，速度快。
4.插入排序：n*n的时间复杂度，稳定排序，原地排序。插入排序是我学的第一个排序，速度还是很快的，特别是在数组已排好了之后，用它的思想来插入一个数据，效率是很高的。因为不用全部排。他的数据交换也很少，只是数据后移，然后放入要插入的数据。（这里不是指调用插入排序，而是用它的思想）。我觉得，在数据大部分都排好了，用插入排序会给你带来很大的方便。数据的移动和交换都很少。
5.冒泡排序，n*n的时间复杂度，稳定排序，原地排序。冒泡排序的思想很不错，一个一个比较，把小的上移，依次确定当前最小元素。因为他简单，稳定排序，而且好实现，所以用处也是比较多的。还有一点就是加上哨兵之后他可以提前退出。
6.选择排序，n*n的时间复杂度， 稳定排序，原地排序。选择排序就是冒泡的基本思想，从小的定位，一个一个选择，直到选择结束。他和插入排序是一个相反的过程，插入是确定一个元素的位置，而选择是确定这个位置的元素。他的好处就是每次只选择确定的元素，不会对很多数据进行交换。所以在数据交换量上应该比冒泡小。
7.插入排序，选择排序，冒泡排序的比较，他们的时间复杂度都是n*n。我觉得他们的效率也是差不多的，我个人喜欢冒泡一些，因为要用它的时候数据多半不多，而且可以提前的返回已经排序好的数组。而其他两个排序就算已经排好了，他也要做全部的扫描。在数据的交换上，冒泡的确比他们都多。呵呵。举例说明插入一个数据在末尾后排序，冒泡只要一次就能搞定，而选择和插入都必须要n*n的复杂度才能搞定。就看你怎么看待咯。
8.合并排序：n*log(n)的时间复杂度， 稳定排序，非原地排序。他的思想是分治，先分成小的部分，排好部分之后合并，因为我们另外申请的空间，在合并的时候效率是0(n)的。速度很快。貌似他的上限是n*log(n)，所以如果说是比较的次数的话，他比快速排序要少一些。对任意的数组都能有效地在n*log(n)排好序。但是因为他是非原地排序，所以虽然他很快，但是貌似他的人气没有快速排序高。
9.堆排序：n*log(n)的时间复杂度， 非稳定排序，原地排序。他的思想是利用的堆这种数据结构，堆可以看成一个完全二叉树，所以在排序中比较的次数可以做到很少。加上他也是原地排序，不需要申请额外的空间，效率也不错。可是他的思想感觉比快速难掌握一些。还有就是在已经排好序的基础上添加一个数据再排序，他的交换次数和比较次数一点都不会减少。虽然堆排序在使用的中没有快速排序广泛，但是他的数据结构和思想真的很不错，而且用它来实现优先队列，效率没得说。堆，还是要好好学习掌握的。
10.希尔排序：n*log(n)的时间复杂度(这里是错误的，应该是n^lamda(1 < lamda < 2), lamda和每次步长选择有关。)， 非稳定排序，原地排序。主要思想是分治，不过他的分治和合并排序的分治不一样，他是按步长来分组的，而不是想合并那样左一半右一半。开始步长为整个的长度的一半。分成nLen/2个组，然后每组排序。接个步长减为原来的一半在分组排序，直到步长为1，排序之后希尔排序就完成了。这个思路很好，据说是插入排序的升级版，所以在实现每组排序的时候我故意用了插入排序。我觉得他是一个特别好的排序方法了。他的缺点就是两个数可能比较多次，因为两个数据会多次分不过他们不会出现数据的交换。效率也是很高的。
11.快速排序，堆排序，合并排序，希尔排序的比较，他们的时间复杂的都是n*log(n)，我认为在使用上快速排序最广泛，他原地排序，虽然不稳定，可是很多情况下排序根本就不在意他是否稳定。他的比较次数是比较小的，因为他把数据分成了大和小的两部分。每次都确定了一个数的位置，所以理论上说不会出现两个数比较两次的情况，也是在最后在交换数据，说以数据交换上也很少。合并排序和堆排序也有这些优点，但是合并排序要申请额外的空间。堆排序堆已经排好的数据交换上比快速多。所以目前快速排序用的要广泛的多。还有他很容易掌握和实现。
12.计数排序：n的时间复杂度，稳定排序，非原地排序。他的思想比较新颖，就是先约定数据的范围不是很大，而且数据都是整数(或能定位到整数)的情况，然后直接申请一个空间。把要排序的数组A的元素值与申请空间B的下标对应，然后B中存放该下标元素值的个数，从而直接定位A中每个元素的位置。这样效率只为n。因为比较很特殊，虽然很快，但是用的地方并不多。
13.基数排序：n的时间复杂度，稳定排序，非原地排序。他的思想是数据比较集中在一个范围，例如都是4位数，都是5位数，或数据有多个关键字，我们先从各位开始排，然后排十位，依次排到最高位，因为我们可以用一个n的方法排一位，所以总的方法为d*n的复杂度。关键字也一样，我们先排第3个关键字，在排第3个关键字，最后排第一个关键字。只有能保证每个关键字在n的时间复杂度完成，那么整个排序就是一个d*n的时间复杂度。所以总的速度是很快的。不过有一点就是要确保关键字能在n的时间复杂度完成。
14.桶排序：n的时间复杂度，稳定排序，非原地排序。主要思路和基数排序一样，也是假设都在一个范围例如概率都在0-1，而且分布还挺均匀，那么我们也是和基数排序一样对一个数把他划分在他指定的区域。然后在连接这些区域就可以了。书上对每个区域使用链表的存储，我认为在寸小区域的时候也会有时间在里面。所以只是理论上的n时间复杂度。这种思路是不错的。呵呵。
15.计数排序，基数排序，桶排序的比较，我觉得他们都很有思想，不过都是在特定情况下才能发挥最大的效果。虽然效率很高，但是用的不会很广泛。他们之间我更喜欢计数排序，来个映射的方式就直接找到了自己的位置，很高明。和基数排序和同排序只是理论上的n时间复杂度，基数排序要确定一个关键字的排序是n复杂度的，桶排序要确定每个区域的排序是n复杂度的。
16.排序算法的最后感悟：黑格尔说过：存在即合理。所以这些排序的算法都是很好的，他确实给了我们思想上的帮助。感谢前人把精华留给了我们。我得到的收获很大，总结一下各自排序的收获：
冒泡：好实现，速度不慢，使用于轻量级的数据排序。
插入排序：也使用于小数据的排序，但是我从他的思想中学到怎么插入一个数据。呵呵，这样就知道在排好的数据里面，不用再排序了，而是直接调用一下插入就可以了。
选择排序：我学会了怎么去获得最大值，最小值等方法。只要选择一下，不就可以了。
合并排序：我学会分而治之的方法，而且在合并两个数组的时候很适用。
堆排序：可以用它来实现优先队列，而且他的思想应该给我加了很多内力。
快速排序：本来就用的最多的排序，对我的帮助大的都不知道怎么说好。
希尔排序：也是分治，让我看到了分治的不同，原来还有这种思想的存在。
计数排序，基数排序，桶排序：特殊情况特殊处理。
插入排序
插入排序主要思想是：把要排序的数字插入到已经排好的数据中。
例如12356是已经排好的序，我们将4插入到他们中，时插入之后也是排好序的。这里显而易见是插入到3的后面。变为123456.实现思路：插入排序就是先是一个有序的数据，然后把要插入的数据插到指定的位置，而排序首先给的就是无序的，我们怎么确定先得到一个有序的数据呢？答案就是：如果只有一个，当然是有序的咯。我们先拿一个出来，他是有序的，然后把数据一个一个插入到其中，那么插入之后是有序的，所以直到最后都是有序的。。结果就出来了！当然在写的时候还是有一个技巧的，不需要开额外的数组，下标从第二个元素开始遍历知道最后一个，然后插入到前面已经有序的数据中。这样就不会浪费空间了。插入排序用处还是很多的，特别是链表中，因为链表是指针存放的，没有数组那么好准确的用下标表示，插入是简单有效的方法。
源代码
1 #include <stdio.h>
2 #include <stdlib.h>
4 //插入排序从下到大，nData为要排序的数据,nNum为数据的个数,该排序是稳定的排序
5 bool InsertionSort(int nData[], int nNum)
6 {
7 for (int i = 1; i < nNum; ++i) //遍历数组，进行插入排序
8 {
9 int nTemp = nData[i];
10 for (int j = 0; j < i; ++j) //对该数，寻找他要插入的位置
11 {
12 if (nData[j] > nTemp) //找到位置，然后插入该位置，之后的数据后移
13 {
14 for (int k = i; k > j; --k) //数据后移
15 {
16 nData[k] = nData[k -1];
17 }
18 nData[j] = nTemp; //将数据插入到指定位置
19 break;
20 }
21 }
22 }
24 return true;
25 }
27 int main()
28 {
29 int nData[10] = {4,10,9,8,7,6,5,4,3,2}; //创建10个数据，测试
30 InsertionSort(nData, 10); //调用插入排序
32 for (int i = 0; i < 10; ++i)
33 {
34 printf("%d ", nData[i]);
35 }
37 printf("\n");
38 system("puase");
39 return 0;
40 }
冒泡排序
冒泡排序的主要思路：
我们把要排序的数组A = {3,4,2,1} 看成一组水泡， <!--[endif]-->就像冒泡一样，轻的在上面，重的在下面，换成数据，就是小的在上面，大的在下面。 我们先把最轻的冒出到顶端，然后冒出第二轻的在最轻的下面，接着冒出第三轻的。依次内推。直到所有都冒出来了为止。
3.我们怎么做到把最轻的放在顶端呢？我们从最底下的数据开始冒，如果比他上面的数据小，就交换（冒上去），然后再用第二第下的数据比较(此时他已经是较轻的一个)，如果他比他上面的小，则交换，把小的冒上去。直到比到第一位置，得到的就是最轻的数据咯，这个过程就像是冒泡一样，下面的和上面的比较，小的冒上去。大的沉下来。
画个图先：
开始：1 和2 比，1比2小，浮上，然后1跟4比，再1跟3比，这样结构就变为1，3，4，2。最小的位置确定了，然后我们确定第二小的，同理2 vs 4, 2 vs 3 得到2， 再确定第3小数据，3 vs 4得到3，最后就是4为最大的数据，我们冒泡就排好了。
注：这里红色的1,2是前一次比较1 vs 2交换的结构。后面也一样。
大概思路就这样了，奉上源代码：
#include <stdio.h>
#include <stdlib.h>
//冒泡排序, pnData要排序的数据， nLen数据的个数
int BubbleSort(int* pnData, int nLen)
{
bool isOk = false; //设置排序是否结束的哨兵
//i从[0,nLen-1)开始冒泡，确定第i个元素
for (int i = 0; i < nLen - 1 && !isOk; ++i)
{
isOk = true; //假定排序成功
//从[nLen - 1, i）检查是否比上面一个小，把小的冒泡浮上去
for (int j = nLen- 1; j > i; --j)
{
if (pnData[j] < pnData[j - 1]) //如果下面的比上面小，交换
{
int nTemp = pnData[j];
pnData[j] = pnData[j - 1];
pnData[j - 1] = nTemp;
isOk = false;
}
}
}
return 1;
}
int main()
{
int nData[10] = {4,10,9,8,7,6,5,4,3,2}; //创建10个数据，测试
BubbleSort(nData, 10); //调用冒泡排序
for (int i = 0; i < 10; ++i)
{
printf("%d ", nData[i]);
}
printf("\n");
system("pause");
return 0;
}
选择排序
选择排序和冒泡排序思路上有一点相似，都是先确定最小元素，再确定第二笑元素，最后确定最大元素。他的主要流程如下：
1.加入一个数组A = {5,3,6,2,4,7}，我们对他进行排序
2.确定最小的元素放在A[0]位置，我们怎么确定呢，首先默认最小元素为5,他的索引为0,然后用它跟3比较，比他打，则认为最小元素为3,他的索引为1，然后用3跟6比，发现比他小，最小元素还是3，然后跟2比，最小元素变成了2，索引为3，然后跟4比，跟7比。当比较结束之后，最小元素也尘埃落定了。就是2，索引为3，然后我们把他放在A[0]处。为了使A[0]原有数据部丢失，我们使A[0](要放的位置) 与A[3]（最小数据的位置）交换。这样就不可以了吗？
3.然后我们在来找第二小元素，放在A[1]，第三小元素，放在A[2]。。当寻找完毕，我们排序也就结束了。
4.不过，在找的时候要注意其实位置，不能在找A[2]的时候，还用A[2]的数据跟已经排好的A[0],A[1]比，一定要跟还没有确定位置的元素比。还有一个技巧就是我们不能每次都存元素值和索引，我们只存索引就可以了，通过索引就能找到元素了。
5.他和冒泡的相似和区别，冒泡和他最大的区别是他发现比他小就交换，把小的放上面，而选择是选择到最小的在直接放在确定的位置。选择也是稳定的排序。
基本思路就这样了，奉上源代码：
#include <stdio.h>
#include <stdlib.h>
//选择排序, pnData要排序的数据， nLen数据的个数
int SelectSort(int* pnData, int nLen)
{
//i从[0,nLen-1)开始选择，确定第i个元素
for (int i = 0; i < nLen - 1; ++i)
{
int nIndex = i;
//遍历剩余数据，选择出当前最小的数据
for (int j = i + 1; j < nLen; ++j)
{
if (pnData[j] < pnData[nIndex])
{
nIndex = j;
}
}
//如果当前最小数据索引不是i，也就是说排在i位置的数据在nIndex处
if (nIndex != i)
{
//交换数据，确定i位置的数据。
int nTemp = pnData[i];
pnData[i] = pnData[nIndex];
pnData[nIndex] = nTemp;
}
}
return 1;
}
int main()
{
int nData[10] = {4,10,9,8,7,6,5,4,3,2}; //创建10个数据，测试
SelectSort(nData, 10); //调用选择排序
for (int i = 0; i < 10; ++i)
{
printf("%d ", nData[i]);
}
printf("\n");
system("pause");
return 0;
}
希尔排序
希尔排序，他的主要思想借用了合并排序的思想。不过他不是左边一半右边一半，而是按照步长来分，随着步长减少，分成的组也越少。然后进行各组的插入排序。主要思路就是这样。
#include <stdio.h>
#include <stdlib.h>
//对单个组排序
int SortGroup(int* pnData, int nLen, int nBegin,int nStep)
{
for (int i = nBegin + nStep; i < nLen; i += nStep)
{
//寻找i元素的位置，
for (int j = nBegin; j < i; j+= nStep)
{
//如果比他小，则这里就是他的位置了
if (pnData[i] < pnData[j])
{
int nTemp = pnData[i];
for (int k = i; k > j; k -= nStep)
{
pnData[k] = pnData[k - nStep];
}
pnData[j] = nTemp;
}
}
}
return 1;
}
//希尔排序, pnData要排序的数据， nLen数据的个数
int ShellSort(int* pnData, int nLen)
{
//以nStep分组，nStep每次减为原来的一半。
for (int nStep = nLen / 2; nStep > 0; nStep /= 2)
{
//对每个组进行排序
for (int i = 0 ;i < nStep; ++i)
{
SortGroup(pnData, nLen, i, nStep);
}
}
return 1;
}
int main()
{
int nData[10] = {4,10,9,8,7,6,5,4,3,2}; //创建10个数据，测试
ShellSort(nData, 10); //调用希尔排序
for (int i = 0; i < 10; ++i)
{
printf("%d ", nData[i]);
}
printf("\n");
system("pause");
return 0;
}
合并排序合并排序的主要思想是：把两个已经排序好的序列进行合并，成为一个排序好的
序列。例如：13579 2468这两个序列，各自都是排好序的，然后我们进行合并，成为123456789这样一个
排好序的序列。貌似这个跟排序关系不大，因为排序给的是一个乱的序列，而合并是合并的两个已经排序
好的序列。且慢，我们可以把需要排序的数据分解成N个子序列，当分解的子序列所包含数据个数为1的时
候，那么这个序列不久是有序了吗？然后再合并。这个就是有名的”分治。例如321分成3，2，1三个序列，1这个序列是有序的啦。同理2，3都是有序的。然后我们逐一的合并他们。3，2合并为23，
然后在23与1合并为123。哈哈，排序成功。合并排序主要思路就是这样了。
但是，问题又出来了，怎么合并两个有序列呢？我相信我应该理解了数组的存储方式，所以直接用数组说
事啦。。我们先把下标定位到各有序子序列的开始，也把合并之后数组的下标定位到最初。那么下标对应
的位置就是他们当前的最小值了。然后拿他们来比较，把更小的那个放到合并之后数组的下标位置。这样
，合并后数组的第一个元素就是他们的最小值了。接着，控制合并后数组的下标后移一个，把比较时小数
字所在序列对应的下标后移一个。这样。下次比较的时候，他得到就是他的第二小，（第一下已经合并了
）就是当前最小值了，在于另一个序列的当前最小值比较，用小的一个放到合并后数组的相应位置。依次
类推。接着当数据都合并玩了结束，合并完成。（这样说忒空泛了，云里雾里的，BS一下以前的我。）
1357 2468 来做例子：
(1回合) 1357 2468 00000(合并后数据空)
(2) 357 2468 100000(0表示空) 因为1 < 2所以把1放到合并后位置中了（这里1并不是丢掉了，而是下
标变为指向3了，1是没有写而已。呵呵。理解为数组的下标指向了3）
(3) 357 468 120000 因为3 > 2，所以把而放进去
(4) 57 468 123000 同理3 < 4
(5) 57 68 1234000 同理5 > 4
(6) 7 68 1234500 同理5 > 6
(7) 7 8 1234560 同理7 > 6
(8) 0(空了) 8 12345670 同理7 < 8
(9) 0 0 12345678 弄最后一个
当然，这些只是思路。并不是一定一成不变的这样。合并OK，那么我们就可以用合并排序了哦！哈哈。。
不过注意，那个321全部弄成一个单个数字，然后一个一个合并这样来合并似乎不是很好，貌似还有更好
的解决方案。哈哈，对了，就是我先分一半来合并。如果这一半是排好序的，那么合并不久简单了吗？但
是我怎么让一般排好序呢。呵呵简单，我一半在分一半合并排序，在分一半合并排序，直到分到两个都是
1个了，就合并，ok!
例如，81726354：
(1)分成9172 6354
(2)把8172 分成 81 和72 把6354分成63和54
(3)81分成8和1,哦能合并了哦。合并为18, 同理72，63，54，也可以分解成单个合并为27,36,45
(4) 现在变为了 18, 27, 36, 45了，这个时侯，18 和27能合并了，合并为1278 同理36,合并为45 3456
(5) 好了最好吧，1278和3456合并为12345678.ok排序成功。
这样把一个问题分解为两个或多个小问题，然后在分解，最后解决小小问题，已达到解决打问题的目的。
1 #include <stdio.h>
2 #include <stdlib.h>
4 //合并排序的合并程序他合并数组nData中位置为[nP,nM) 和[nM,nR).这个是更接近标准的思路
5 bool MergeStandard(int nData[], int nP, int nM, int nR)
6 {
7 int n1 = nM - nP; //第一个合并数据的长度
8 int n2 = nR - nM; //第二个合并数据的长度
10 int *pnD1 = new int[n1 + 1]; //申请一个保存第一个数据的空间
11 int *pnD2 = new int[n2 + 1]; //申请二个保存第一个数据的空间
13 for (int i = 0; i < n1; ++i) //复制第一个数据到临时空间里面
14 {
15 pnD1[i] = nData[nP + i];
16 }
17 pnD1[n1] = INT_MAX; //将最后一个数据设置为最大值(哨兵)
19 for (int i = 0; i < n2; ++i) //复制第二个数据到临时空间里面
20 {
21 pnD2[i] = nData[nM + i];
22 }
23 pnD2[n2] = INT_MAX; //将最后一个数据设置为最大值(哨兵)
25 n1 = n2 = 0;
27 while(nP < nR)
28 {
29 nData[nP++] = pnD1[n1] < pnD2[n2] ? pnD1[n1++] : pnD2[n2++]; //取出当前最小值到指定位置
30 }
32 delete pnD1;
33 delete pnD2;
34 return true;
35 }
37 //合并排序的合并程序他合并数组nData中位置为[nP,nM) 和[nM,nR).
38 bool Merge(int nData[], int nP, int nM, int nR)
39 {
40 //这里面有几个注释语句是因为当时想少写几行而至。看似短了，其实运行时间是一样的，而且不易阅读。
42 int nLen1 = nM - nP; //第一个合并数据的长度
43 int nLen2 = nR - nM; //第二个合并数据的长度
44 int* pnD1 = new int[nLen1]; //申请一个保存第一个数据的空间
45 int* pnD2 = new int[nLen2]; //申请一个保存第一个数据的空间
46
47 int i = 0;
48 for ( i = 0; i < nLen1; ++i) //复制第一个数据到临时空间里面
49 {
50 pnD1[i] = nData[nP + i];
51 }
53 int j = 0;
54 for (j = 0; j < nLen2; ++j) //复制第二个数据到临时空间里面
55 {
56 pnD2[j] = nData[nM + j];
57 }
59 i = j = 0;
60 while (i < nLen1 && j < nLen2)
61 {
62 //nData[nP++] = pnD1[i] < pnD2[j] ? pnD1[i++] : pnD2[j++]; //取出当前最小值添加到数据中
64 if (pnD1[i] < pnD2[j]) //取出最小值，并添加到指定位置中，如果pnD1[i] < pnD2[j]
65 {
66 nData[nP] = pnD1[i]; //取出pnD1的值，然后i++，定位到下一个个最小值。
67 ++i;
68 }
69 else //这里同上
70 {
71 nData[nP] = pnD2[j];
72 ++j;
73 }
74 ++nP; //最后np++，到确定下一个数据
75 }
77 if (i < nLen1) //如果第一个数据没有结束（第二个数据已经结束了）
78 {
79 while (nP < nR) //直接把第一个剩余的数据加到nData的后面即可。
80 {
81 //nData[nP++] = pnD1[i++];
82 nData[nP] = pnD1[i];
83 ++nP;
84 ++i;
85 }
86 }
87 else //否则（第一个结束，第二个没有结束）
88 {
89 while (nP < nR) //直接把第一个剩余的数据加到nData的后面即可。
90 {
91 //nData[nP++] = pnD2[j++];
92 nData[nP] = pnD2[j];
93 ++nP;
94 ++j;
95 }
96 }
98 delete pnD1; //释放申请的内存空间
99 delete pnD2;
100
101 return true;
102 }
104 //合并的递归调用,排序[nBegin, nEnd)区间的内容
105 bool MergeRecursion(int nData[], int nBegin, int nEnd)
106 {
107 if (nBegin >= nEnd - 1) //已经到最小颗粒了,直接返回
108 {
109 return false;
110 }
112 int nMid = (nBegin + nEnd) / 2; //计算出他们的中间位置，便于分治
113 MergeRecursion(nData, nBegin, nMid); //递归调用，合并排序好左边一半
114 MergeRecursion(nData, nMid, nEnd); //递归调用，合并排序好右边一半
115 //Merge(nData, nBegin, nMid, nEnd); //将已经合并排序好的左右数据合并，时整个数据排序完成
116 MergeStandard(nData, nBegin, nMid, nEnd);//(用更接近标准的方法合并)
118 return true;
119 }
121 //合并排序
122 bool MergeSort(int nData[], int nNum)
123 {
124 return MergeRecursion(nData, 0, nNum); //调用递归，完成合并排序
125 }
127 int main()
128 {
129 int nData[10] = {4,10,3,8,5,6,7,4,9,2}; //创建10个数据，测试
131 MergeSort(nData, 10);
132 for (int i = 0; i < 10; ++i)
133 {
134 printf("%d ", nData[i]);
135 }
137 printf("\n");
138 system("pause");
139 return 0;
140 }
堆排序
#include <stdio.h>
#include <stdlib.h>
//交换两个整数。注意一定要if判断是否两个相等，如果
//不相等才交换，如果相等也交换会出错的。a^a = 0
inline void Swap(int& a, int& b)
{
if (a != b)
{
a^= b;
b^= a;
a^= b;
}
}
//维持一个最大堆
int Heapify(int* npData, int nPos, int nLen)
{
int nMax = -1; //暂存最大值
int nChild = nPos * 2; //他的左孩子位置
while(nChild <= nLen) //判断他是否有孩子
{
nMax = npData[nPos]; //是当前最大值为他
if (nMax < npData[nChild]) //与左孩子比较
{
nMax = npData[nChild]; //如果比左孩子小，就时最大值为左孩子
}
//同理与右孩子比较，这里要注意，必须要保证有右孩子。
if (nChild + 1 <= nLen && nMax < npData[nChild + 1])
{
++nChild; //赋值最大值的时候把孩子变为右孩子，方便最后的数据交换
nMax = npData[nChild];
}
if (nMax != npData[nPos]) //判断是否该节点比孩子都打，如果不大
{
Swap(npData[nPos], npData[nChild]); //与最大孩子交换数据
nPos = nChild; //该节点位置变为交换孩子的位置
nChild *= 2; //因为只有交换后才使不满足堆得性质。
}
else //都最大了，满足堆得性质了。退出循环
{
break;
}
}
return 1; //维持结束。
}
//建立一个堆
int BuildHeap(int* npData, int nLen)
{
//从nLen / 2最后一个有叶子的数据开始，逐一的插入堆，并维持堆得平衡。
//因为堆是一个完全二叉树，所以nlen/2+1- nLen之间肯定都是叶子。
//叶子还判断什么呢。只有一个数据，肯定满足堆得性质咯。
for (int i = nLen / 2; i >= 1; --i)
{
Heapify(npData, i, nLen);
}
return 1;
}
//堆排序
int HeapSort(int* npData, int nLen)
{
BuildHeap(npData, nLen); //建立一个堆。
while(nLen >= 1) //逐一交和第一个元素交换数据到最后
{ //完成排序
Swap(npData[nLen], npData[1]);
--nLen;
Heapify(npData, 1, nLen);//交换之后一定要维持一下堆得性质。
} //不然小的成第一个元素,就不是堆了。
return 1;
}
//main函数，
int main()
{
int nData[11] = {0,9,8,7,6,5,4,3,2,1,0}; //测试数据，下标从1开始哦。
HeapSort(nData, 10); //堆排序
for (int i = 1; i <= 10; ++i) //输出排序结果。
{
printf("%d ", nData[i]);
}
printf("\n");
system("pause");
return 0;
}
用堆排序实现优先队列
1.一个是他是一个数组（当然你也可以真的用链表来做。）。
2.他可以看做一个完全二叉树。注意是完全二叉树。所以他的叶子个数刚好是nSize / 2个。
3.我使用的下标从1开始，这样好算，如果节点的位置为i,他的父节点就是i/2,他的左孩子结点就是i*2,右孩子结点就是i*2+1，如果下标从0开始，要复杂一点。
4.他的父节点一定不比子节点小（我所指的是最大堆）。
由这些性质就可以看出堆得一些优点：
1.可以一下找到最大值，就在第一个位置heap[1].
2.维持堆只需要log(2,n)(n是数据个数)的复杂度，速度比较快。他只需要比较父与子之间的大小关系，所以比较次数就是树的高度，而他是一个完全二叉树，所以比较次数就是log(2,n)。
具体实现：
具体实现就看看源代码吧！
#include <stdio.h>
#include <stdlib.h>
//定义一个堆得结构体，
struct MyHeap
{
int* pnData; //指向数据的指针
int nSize; //当前堆中的元素个数
};
//调整数据，维持堆得性质，这个和上次heapify的作用一样
//只是这个时从子道父节点这样的判断而已。
int IncreaseKey(MyHeap* pHeap, int nPos)
{
//循环和他父节点判断，只要 nPos > 1他就有父节点
while(nPos > 1)
{
int nMax = pHeap->pnData[nPos];
int nParent = nPos / 2;
//如果他比父节点大，交换数据，并使判断进入父节点
//（因为只有父节点可能会影响堆得性质。他的数据改变了。）
if (nMax > pHeap->pnData[nParent])
{
pHeap->pnData[nPos] = pHeap->pnData[nParent];
pHeap->pnData[nParent] = nMax;
nPos = nParent;
}
else //否则堆没有被破坏，退出循环
{
break;
}
}
return 1;
}
//插入数据，这里pnHeap为要插入的队，nLen为当前堆得大小。
//nData为要插入的数据，这里注意报保证堆得空间足够。
int Insert(MyHeap* pHeap, int nData)
{
++pHeap->nSize; //添加数据到末尾
pHeap->pnData[pHeap->nSize] = nData;
IncreaseKey(pHeap, pHeap->nSize);
return 1;
}
//弹出堆中对大元素，并使堆得个数减一
int PopMaxHeap(MyHeap* pHeap)
{
int nMax = pHeap->pnData[1]; //得到最大元素
//不要忘记维持堆得性质，因为最大元素已经弹出了，主要思路就是
//同他最大孩子填充这里。
int nPos = 1; //起始位1，因为他弹出，所以是这里开始破坏堆得性质的
int nChild = nPos * 2; //他的左孩子的位置，
//循环填充，用最大孩子填充父节点
while(nChild <= pHeap->nSize)
{
int nTemp = pHeap->pnData[nChild];
if (nChild + 1 <= pHeap->nSize &&
nTemp < pHeap->pnData[nChild + 1])
{
++nChild;
nTemp = pHeap->pnData[nChild];
}
pHeap->pnData[nPos] = nTemp;
nPos = nChild;
nChild *= 2;
}
//最好一个用最末尾的填充。
pHeap->pnData[nPos] = pHeap->pnData[pHeap->nSize];
--pHeap->nSize; //堆个数量减一
return nMax; //返回最大值。
}
//程序入口main
int main()
{
MyHeap myHeap; //定义一个堆
myHeap.pnData = (int*)::malloc(sizeof(int) *11); //申请数据空间
myHeap.nSize = 0; //初始大小为0
for (int i = 1; i <= 10; ++i) //给优先队列堆里添加数据
{
Insert(&myHeap, i);
}
for (int i = 1; i <= 10; ++i) //测试优先队列是否建立成功
{
printf("%d ", myHeap.pnData[i]);
}
printf("\n");
while(myHeap.nSize > 0) //逐一弹出队列的最大值。并验证
{
printf("%d ", PopMaxHeap(&myHeap));
}
printf("\n");
::free(myHeap.pnData); //最后不要忘记释放申请的空间
system("pause");
return 0;
}
基数排序
据说他的时间复杂度也是O(n)，他的思路就是：
没有计数排序那么理想，我们的数据都比较集中，都比较大，一般是4，5位。基本没有小的数据。
那我们的处理很简单，你不是没有小的数据嘛。我给一个基数，例如个位，个位都是[0-10)范围内的。先对他进行归类，把小的放上面，大的放下面，然后个位排好了，在来看10位，我们也这样把小的放上面，大的放下面，依次内推，直到最高位排好。那么不就排好了吗？我们只需要做d(基数个数)的循环就可以了。时间复杂度相当于O(d * n) 因为d为常量，例如5位数，d就是5.所以近似为O(n)的时间复杂度。这次自己写个案例：
这里只需循环3次就出结果了。
<!--[if !supportLists]-->3. <!--[endif]-->但是注意，我们必须要把个位排好。但是个位怎么排呢？这个是个问题。书上说的是一叠一叠的怎么合并，我是没有理解的。希望知道的有高手教我一下。
我是用的一个计数排序来排各位的，然后排十位。效率应该也低不到哪里去。
思路就这样咯。奉上源代码：
#include <stdio.h>
#include <stdlib.h>
//计数排序，npRadix为对应的关键字序列，nMax是关键字的范围。npData是具体要
//排的数据，nLen是数据的范围，这里必须注意npIndex和npData对应的下标要一致
//也就是说npIndex[1] 所对应的值为npData[1]
int RadixCountSort(int* npIndex, int nMax, int* npData, int nLen)
{
//这里就不用说了，计数的排序。不过这里为了是排序稳定
//在标准的方法上做了小修改。
int* pnCount = (int*)malloc(sizeof(int)* nMax); //保存计数的个数
for (int i = 0; i < nMax; ++i)
{
pnCount[i] = 0;
}
for (int i = 0; i < nLen; ++i) //初始化计数个数
{
++pnCount[npIndex[i]];
}
for (int i = 1; i < 10; ++i) //确定不大于该位置的个数。
{
pnCount[i] += pnCount[i - 1];
}
int * pnSort = (int*)malloc(sizeof(int) * nLen); //存放零时的排序结果。
//注意：这里i是从nLen-1到0的顺序排序的，是为了使排序稳定。
for (int i = nLen - 1; i >= 0; --i)
{
--pnCount[npIndex[i]];
pnSort[pnCount[npIndex[i]]] = npData[i];
}
for (int i = 0; i < nLen; ++i) //把排序结构输入到返回的数据中。
{
npData[i] = pnSort[i];
}
free(pnSort); //记得释放资源。
free(pnCount);
return 1;
}
//基数排序
int RadixSort(int* nPData, int nLen)
{
//申请存放基数的空间
int* nDataRadix = (int*)malloc(sizeof(int) * nLen);
int nRadixBase = 1; //初始化倍数基数为1
bool nIsOk = false; //设置完成排序为false
//循环，知道排序完成
while (!nIsOk)
{
nIsOk = true;
nRadixBase *= 10;
for (int i = 0; i < nLen; ++i)
{
nDataRadix[i] = nPData[i] % nRadixBase;
nDataRadix[i] /= nRadixBase / 10;
if (nDataRadix[i] > 0)
{
nIsOk = false;
}
}
if (nIsOk) //如果所有的基数都为0，认为排序完成，就是已经判断到最高位了。
{
break;
}
RadixCountSort(nDataRadix, 10, nPData, nLen);
}
free(nDataRadix);
return 1;
}
int main()
{
//测试基数排序。
int nData[10] = {123,5264,9513,854,9639,1985,159,3654,8521,8888};
RadixSort(nData, 10);
for (int i = 0; i < 10; ++i)
{
printf("%d ", nData[i]);
}
printf("\n");
system("pause");
return 0;
}
计数排序：
貌似计数排序的复杂度为o(n)。很强大。他的基本思路为：
<!--[if !supportLists]-->1. <!--[endif]-->我们希望能线性的时间复杂度排序，如果一个一个比较，显然是不实际的，书上也在决策树模型中论证了，比较排序的情况为nlogn的复杂度。
<!--[if !supportLists]-->2. <!--[endif]-->既然不能一个一个比较，我们想到一个办法，就是如果我在排序的时候就知道他的位置，那不就是扫描一遍，把他放入他应该的位置不就可以了嘛。
<!--[if !supportLists]-->3. <!--[endif]-->要知道他的位置，我们只需要知道有多少不大于他不就可以了吗？
<!--[if !supportLists]-->4. <!--[endif]-->以此为出发点，我们怎么确定不大于他的个数呢？我们先来个约定，如果数组中的元素都比较集中，都在[0, max]范围内。我们开一个max的空间b数组，把b数组下标对应的元素和要排序的A数组下标对应起来。这样不就可以知道不比他大的有多少个了吗？我们只要把比他小的位置元素个数求和，就是不比他大的。例如：A={3,5,7};我们开一个大小为8的数组b，把a[0] = 3 放入b[3]中，使b[3] = 0; 同理 b[5] = 1; b[7] = 2;其他我们都设置为-1，哈哈我们只需要遍历一下b数组，如果他有数据，就来出来，铁定是当前最小的。如果要知道比a[2]小的数字有多少个，值只需要求出b[0] – b[6]的有数据的和就可以了。这个0(n)的速度不是盖得。
<!--[if !supportLists]-->5. <!--[endif]-->思路就是这样咯。但是要注意两个数相同的情况A = {1,2,3,3,4}，这种情况就不可以咯，所以还是有点小技巧的。
<!--[if !supportLists]-->6. <!--[endif]-->处理小技巧：我们不把A的元素大小与B的下标一一对应，而是在B数组对应处记录该元素大小的个数。这不久解决了吗。哈哈。例如A = {1,2,3,3,4}我们开大小为5的数组b;记录数组A中元素值为0的个数为b[0] = 0, 记录数组A中元素个数为1的b[1] = 1,同理b[2] = 1, b[3] = 2, b[4] = 1;好了，这样我们就知道比A[4](4)小的元素个数是多少了：count = b[0] + b[1] + b[2] + b[3] = 4;他就把A[4]的元素放在第4个位置。
还是截张书上的图：
<!--[if !vml]-->
<!--[endif]-->
再次推荐《算法导论》这本书，在我的上次的随笔中有下载链接。哈哈。真正支持还是需要买一下纸版。呵呵。
<!--[if !supportLists]-->7. 不过在编程的时候还是要注意细节的，例如我不能每次都来算一下比他小的个数。呵呵，思路就这样了。奉上源代码：
#include <stdio.h>
#include <stdlib.h>
//计数排序
int CountSort(int* pData, int nLen)
{
int* pCout = NULL; //保存记数数据的指针
pCout = (int*)malloc(sizeof(int) * nLen); //申请空间
//初始化记数为0
for (int i = 0; i < nLen; ++i)
{
pCout[i] = 0;
}
//记录排序记数。在排序的值相应记数加1。
for (int i = 0; i < nLen; ++i)
{
++pCout[pData[i]]; //增
}
//确定不比该位置大的数据个数。
for (int i = 1; i < nLen; ++i)
{
pCout[i] += pCout[i - 1]; //不比他大的数据个数为他的个数加上前一个的记数。
}
int* pSort = NULL; //保存排序结果的指针
pSort = (int*)malloc(sizeof(int) * nLen); //申请空间
for (int i = 0; i < nLen; ++i)
{
//把数据放在指定位置。因为pCout[pData[i]]的值就是不比他大数据的个数。
//为什么要先减一，因为pCout[pData[i]]保存的是不比他大数据的个数中包括了
//他自己，我的下标是从零开始的!所以要先减一。
--pCout[pData[i]]; //因为有相同数据的可能，所以要把该位置数据个数减一。
pSort[pCout[pData[i]]] = pData[i];
}
//排序结束，复制到原来数组中。
for (int i = 0; i < nLen; ++i)
{
pData[i] = pSort[i];
}
//最后要注意释放申请的空间。
free(pCout);
free(pSort);
return 1;
}
int main()
{
int nData[10] = {8,6,3,6,5,8,3,5,1,0};
CountSort(nData, 10);
for (int i = 0; i < 10; ++i)
{
printf("%d ", nData[i]);
}
printf("\n");
system("pause");
return 0;
}
快速排序
(一) 实现
快速排序的实现基于分治法，具体分为三个步骤。假设待排序的序列为L[m..n]。
分解：序列L[m .. n]被划分成两个可能为空的子序列L[m .. pivot-1]和L[pivot+1 .. n]，使L[m .. pivot-1]的每个元素均小于或等于L[pivot]，同时L[pivot+1.. n]的每个元素均大于L[pivot]。其中L[pivot]称为这一趟分割中的主元（也称为枢轴、支点）。
解决：通过递归调用快速排序，对子序列L[m .. pivot-1]和L[pivot+1 .. r]排序。
合并：由于两个子序列是就地排序的，所以对它们的合并不需要操作，整个序列L[m .. n]已排好序。
(二)概述
快速排序(Quick Sort)是一种有效的排序算法。虽然算法在最坏的情况下运行时间为O(n^2)，但由于平均运行时间为O(nlogn)，并且在内存使用、程序实现复杂性上表现优秀，尤其是对快速排序算法进行随机化的可能，使得快速排序在一般情况下是最实用的排序方法之一。
快速排序被认为是当前最优秀的内部排序方法。
(三)性质
内部排序
快速排序是一种内部排序方法。也就是说快速排序的排序对象是读入内存的数据。
比较排序
快速排序确定元素位置的方法基于元素之间关键字大小的比较。
所有基于比较方法的排序方法的时间下界不会低于O(nlgn)。这个结论的具体证明，请参考有关算法的书籍，例如《算法导论》（第一版）第8章（第二版在第七章QuickSort)。
在理想情况下，能严格地达到O(nlgn)的下界。一般情况下，快速排序与随机化快速排序的平均情况性能都达到了O(nlgn)。
不稳定性
快速排序是一种不稳定的排序方法。简单地说，元素a1, a2的关键字有a1.key=a2.key，则不稳定的排序方法不能保证a1, a2在排序后维持原来的位置先后关系。
原地排序
在排序的具体操作过程中，除去程序运行实现的空间消费（例如递归栈），快速排序算法只需消耗确定数量的空间（即S(1)，常数级空间）。
这个性质的意义，在于在内存空间受到限制的系统（例如MCU）中，快速排序也能够很好地工作。
(四)时空复杂度
快速排序每次将待排序数组分为两个部分，在理想状况下，每一次都将待排序数组划分成等长两个部分，则需要logn次划分。
而在最坏情况下，即数组已经有序或大致有序的情况下，每次划分只能减少一个元素，快速排序将不幸退化为冒泡排序，所以快速排序时间复杂度下界为O(nlogn)，最坏情况为O(n^2)。在实际应用中，快速排序的平均时间复杂度为O(nlogn)。
快速排序在对序列的操作过程中只需花费常数级的空间。空间复杂度S(1)。
但需要注意递归栈上需要花费最少logn 最多n的空间。
(五)随机化算法
快速排序的最坏情况基于每次划分对主元的选择。基本的快速排序选取第一个元素作为主元。这样在数组已经有序的情况下，每次划分将得到最坏的结果。一种比较常见的优化方法是随机化算法，即随机选取一个元素作为主元。这种情况下虽然最坏情况仍然是O(n^2)，但最坏情况不再依赖于输入数据，而是由于随机函数取值不佳。实际上，随机化快速排序得到理论最坏情况的可能性仅为1/(2^n)。所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn)的期望时间复杂度。一位前辈做出了一个精辟的总结：“随机化快速排序可以满足一个人一辈子的人品需求。”
随机化快速排序的唯一缺点在于，一旦输入数据中有很多的相同数据，随机化的效果将直接减弱。对于极限情况，即对于n个相同的数排序，随机化快速排序的时间复杂度将毫无疑问的降低到O(n^2)。
(六)减少递归栈使用的优化
快速排序的实现需要消耗递归栈的空间，而大多数情况下都会通过使用系统递归栈来完成递归求解。在元素数量较大时，对系统栈的频繁存取会影响到排序的效率。
一种常见的办法是设置一个阈值，在每次递归求解中，如果元素总数不足这个阈值，则放弃快速排序，调用一个简单的排序过程完成该子序列的排序。这样的方法减少了对系统递归栈的频繁存取，节省了时间的消费。
一般的经验表明，阈值取一个较小的值，排序算法采用选择、插入等紧凑、简洁的排序。一个可以参考的具体方案：阈值T=10，排序算法用选择排序。
阈值不要太大，否则省下的存取系统栈的时间，将会被简单排序算法较多的时间花费所抵消。
另一个可以参考的方法，是自行建栈模拟递归过程。但实际经验表明，收效明显不如设置阈值。
(七)C例程
以下是C语言权威《The C Programming Language》中的例程，在这个例程中，对于数组v的left到right号元素以递增顺序排序。
//Qsort.c by Tydus.
#include <stdio.h>
int arr[] = {14,10,11,5,6,15,0,15,16,14,0,8,17,15,7,19,17,1,18,7};
/* swap函数：交换v[k]与v[j]的值 */
inline void swap(int v[], int k, int j)
{
int temp;
temp = v[k];
v[k] = v[j];
v[j] = temp;
}
void qsort(int v[], int left, int right)
{
int j, last;
if (left >= right) /* 若数组包含的元素个数少于两个 */
return; /* 则不执行任何操作 */
swap(v, left, (left + right)/2); /* 将划分子集的元素移动到V[0] */
last=left; /* 用last记录中比关键字小间的最右位置*/
for (j = left+1; j <= right; j++) /* 划分子集 */
{
if (v[j] < v[left])
{
swap(v, last++, j);
}
} /*小小。。。。关键字大大大大*/
qsort(v, left, last-1);
qsort(v, last+1, right);
}
void main()
{
int j;
qsort(arr, 0, 19);
for(j=0; j<=19; j++)
{
printf("%d ", arr[j]);
}
printf("\n");
}
(八)消除递归的快速排序
传统的快速排序是递归的，这就会受到递归栈深度的限制。比如在一台普通的PC上，当待排序元素达到10^6以上时，传统的递归快排会导致栈溢出异常，或者一个莫名其妙的错误结果。所以，对于巨大的数据规模，将快速排序消除递归是十分必要的。而消除递归，又将带来巨大的性能提升，把系统级的消耗降到最低。
消除递归的方法，就是模拟栈操作。但是从代码可以看出，这种模拟的消耗几乎可以忽略不计。因此消除递归的快排的效率是有保障的。
（虽然下面的代码没有使用随机化，但经过测试，它是目前所有快排编写方法中，效率最高，速度最快的！）
#define MAXARRAY 10000
#define PUSH(A,B) {sl[sp]=A;sr[sp]=B;sp++;}
#define POP(A,B) {sp--;A=sl[sp];B=sr[sp];}
void quicksort(int a[],int l,int r){
static int sl[MAXARRAY], sr[MAXARRAY], sp;
int i,j,p,t;
sp=0;
PUSH(l,r);
while(sp){
POP(l,r);
i=l;j=r;p=a[(i+j)/2];
while(i<=j){
while(a[i]<p)i++;
while(a[j]>p)j--;
if(i<=j){
t=a[i];a[i]=a[j];a[j]=t;
i++;j--;
}
}
if(l<j)PUSH(l,j);
if(i<r)PUSH(i,r);
}
}
(九)C++例程
以下是一个用C++编写的快速排序程序。虽然C标准库中提供了快速排序，但作为快速排序的介绍，原理程序的代码更加有助于对快速排序运行过程的分析。
在这个例程中，对于数组x的0~n-1号元素的排序，初始调用为：quicksort(x, 0, n-1);
int quicksort_partition(int L[], int Lbb, int Ubb)
{
//随机化
int iRndPivID;
srand(unsigned(time(0)));
iRndPivID = (rand() % (Ubb - Lbb + 1)) + Lbb;
swap(L[iRndPivID], L[Ubb]);
//快排
int iPivValue;
int i;
int iPivPos;
iPivValue = L[Ubb];
iPivPos = Lbb - 1;
for (i=Lbb; i<=Ubb-1; i++)
{
if (L[ i ] <= iPivValue)
{
iPivPos++;
swap(L[iPivPos], L[ i ]);
}
}
iPivPos++;
swap(L[iPivPos], L[Ubb]);
return iPivPos;
}
void quicksort(int L[], int Lbb, int Ubb)
{
int iPiv;
if (Lbb < Ubb)
{
iPiv = quicksort_partition(L, Lbb, Ubb);
quicksort(L, Lbb, iPiv - 1);
quicksort(L, iPiv + 1, Ubb);
}
return;
}
(十)使用C++标准库的快速排序函数
C++的标准库stdlib.h中提供了快速排序函数。
请在使用前加入对stdlib.h的引用：#include <cstdlib> 或 #include <stdlib.h>
qsort(void* base, size_t num, size_t width, int(*)compare(const void* elem1, const void* elem2))
参数表
*base: 待排序的元素（数组，下标0起）。
num: 元素的数量。
width: 每个元素的内存空间大小（以字节为单位）。可用sizeof()测得。
int(*)compare: 指向一个比较函数。*elem1 *elem2: 指向待比较的数据。
比较函数的返回值
返回值是int类型，确定elem1与elem2的相对位置。
elem1在elem2右侧返回正数，elem1在elem2左侧返回负数。
控制返回值可以确定升序/降序。
一个升序排序的例程：
int Compare(const void *elem1, const void *elem2)
{
return *((int *)(elem1)) - *((int *)(elem2));
}
int main()
{
int a[100];
qsort(a, 100, sizeof(int), Compare);
return 0;
}
(十一)PASCAL例程
1. 基本思想：
在当前无序区R[1..H]中任取一个数据元素作为比较的"基准"(不妨记为X)，用此基准将当前无序区划分为左右两个较小的无序区：R[1..I-1]和R[I+1..H]，且左边的无序子区中数据元素均小于等于基准元素，右边的无序子区中数据元素均大于等于基准元素，而基准X则位于最终排序的位置上，即R[1..I-1]≤X.Key≤R[I+1..H](1≤I≤H)，当R[1..I-1]和R[I+1..H]均非空时，分别对它们进行上述的划分过程，直至所有无序子区中的数据元素均已排序为止。
2. 排序过程：
【示例】：
初始关键字 [10 5 8 4 6 1 5 4 7 2]（n为10）
第一次交换后[2 5 4 4 5 1] 6[ 8 10 ]
第二次交换后[2 1 4] 4 [5 5] 6 8[10 ]
第三次交换后1 2 4 4 5 5 6 8 10
最后的排序结果 1 2 4 4 5 5 6 8 10
type xxx=array[1..1000000] of longint;
var a,n;longint;
x:xxx;
procedure qsort(var x:xxx;l,r:longint);{x为要排序的数组，l为数组的要排序部分的起始位置，r为数组的要排序部分的终点位置}
var n,i,j,mid:longint;
begin
i:=l;{右边起点值}
j:=r;{左边终点值}
mid:=x[(i+j) div 2]; {基准数（用随机化更快）}
repeat
while (i<=j) and (x<mid) do inc(i);{若左边的数比基准数小且左、右区未定，保留在左边}
while (i<=j) and (x[j]>mid) do dec(j);{若右边的数比基准数大且左、右区未定，保留在右边}
if i<=j then{若左、右区未定（定且 左>基准数>右），交换}
begin
n:=x;
x:=x[j];
x[j]:=n;
inc(i);
dec(j);
end;
until i>j;{直到左右区已定（即左边终点j小于右边起点i）}
if i<r then qsort(x,i,r);{若右边多于一个数，快排右边}
if j>l then qsort(x,l,j);{若左边多于一个数，快排左边}
end;
begin
readln(n);{读入要排序的数的个数}
for a:=1 to n do read(x[a]);{读入要排序的书}
writeln;
qsort(x,1,n);{排序程序}
for a:=1 to n-1 do write(x[a],' ');{输出排好序得数}
writeln(x[n]);
end.
(十二)C语言随机化快排模块化代码
#include "stdio.h"
#include "stdlib.h"
#include "time.h"
Location(int *a,int low,int high)
{
int key,temp,x;
srand((unsigned)time(0));
x=rand()%(high-low+1)+low;
key=a[x];
while(low<high)
{
while(x<high&&key<=a[high])high--;
temp=a[high];
a[high]=key;
a[x]=temp;
x=high;
while(low<x&&key>=a[low])low++;
temp=a[low];
a[low]=key;
a[x]=temp;
x=low;
}
return low;
}
Qsort(int *a,int low,int high)
{
int locat,i;
if(low>=high)return 0;
locat=Location(a,low,high);
Qsort(a,low,locat-1);
Qsort(a,locat+1,high);
}
(十三)快速排序的JAVA实现
import java.util.Arrays;
public class QuickSort {
public static void quickSort(int[] array) {
quickSort(array, 0, array.length - 1);
}
private static void quickSort(int[] array, int low, int high) {
if (low < high) {
int p = partition(array, low, high);
quickSort(array, low, p - 1);
quickSort(array, p + 1, high);
}
}
private static int partition(int[] array, int low, int high) {
int s = array[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (array[j] < s) {
i++;
swap(array, i, j);
}
}
swap(array, ++i, high);
return i;
}
private static void swap(int[] array, int i, int j) {
int temp;
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
/**
* @param args
*/
public static void main(String[] args) {
int[] arr ={12,3,5,4,78,67,1,33,1,1,1};
quickSort(arr);
System.out.println(Arrays.toString(arr));
}
}
二分法插入排序
#include<stdio.h>
#define maxsize 100
typedef int datatype;
typedef struct{
datatype a[maxsize];
int size;
}sequence_list;
void init_sequence_list(sequence_list *slt)
{
slt->size=1;
}
void insert_sequence_list(sequence_list *slt,datatype x)
{
if(slt->size==maxsize)
printf("表满，无法插入!");
slt->a[slt->size]=x;
slt->size++;
}
void print_sequence_list(sequence_list slt)
{
int i;
if(slt.size==1)
printf("\n表是空的!");
else
for(i=1;i<slt.size;i++)
printf("%5d",slt.a[i]);
}
void insert_num_sequence_list(sequence_list *slt)
{
int x,i,j=1;
printf("\n请输入插入数的个数:");
scanf("%d",&i);
do
{
scanf("%d",&x);
insert_sequence_list(slt,x);
j++;
}while(j<=i);
}
void binarysort(sequence_list *slt)
{
int i,j,left,right,mid;
for(i=2;i<=slt->size;i++)
{
slt->a[0]=slt->a[i];
left=1;
right=i-1;
while(left<=right)
{
mid=(left+right)/2;
if(slt->a[0]<slt->a[mid])
right=mid-1;
else
left=mid+1;
}
for(j=i-1;j>=left;j--)
slt->a[j+1]=slt->a[j];
slt->a[left]=slt->a[0];
}
}
void main()
{
int i;
sequence_list slt;
init_sequence_list(&slt);
insert_num_sequence_list(&slt);
printf("表为:\n");
print_sequence_list(slt);
printf("\n");
binarysort(&slt);
for(i=2;i<=slt.size;i++)
printf("%5d",slt.a[i]);
printf("\n");
}