sorting算法

排序算法：

冒泡排序：

冒泡排序算法的运作如下：

比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <math.h>
 4 
 5 int main()
 6 {
 7     int a[10];
 8     for(int i=0;i<10;i++)
 9         a[i]=random()/10000;
10     int m;
11     for(int i=0;i<10;i++)
12     {
13         for(int j=0;j<10-i;j++)
14         {
15             if(a[j-1]>a[j])
16             {
17                 m=a[j-1];
18                 a[j-1]=a[j];
19                 a[j]=m;
20             }
21         }
22     }
23     for(int i=0;i<10;i++)
24         printf("%d
",a[i]);
25     printf("
");
26     return 0;
27 }

View Code

不过针对上述代码还有两种优化方案。

优化1：某一趟遍历如果没有数据交换，则说明已经排好序了，因此不用再进行迭代了。用一个标记记录这个状态即可。
优化2：记录某次遍历时最后发生数据交换的位置，这个位置之后的数据显然已经有序，不用再排序了。因此通过记录最后发生数据交换的位置就可以确定下次循环的范围了。

优化1:

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <math.h>
 4 
 5 int main()
 6 {
 7     int a[10];
 8     for(int i=0;i<10;i++)
 9         a[i]=random()/10000;
10     int m;
11     bool flag;
12     for(int i=0;i<10;i++)
13     {
14         flag=false;
15         for(int j=0;j<10-i;j++)
16         {
17             if(a[j-1]>a[j])
18             {
19                 flag=true;
20                 m=a[j-1];
21                 a[j-1]=a[j];
22                 a[j]=m;
23             }
24         }
25         if(!flag)
26             break;
27     }
28     for(int i=0;i<10;i++)
29         printf("%d
",a[i]);
30     printf("
");
31     return 0;
32 }

View Code

优化2:

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <math.h>
 4 
 5 int main()
 6 {
 7     int a[10];
 8     for(int i=0;i<10;i++)
 9         a[i]=random()/10000;
10     int m;
11     int loc=10;
12     int loc1=10;
13     bool flag;
14     for(int i=0;i<10;i++)
15     {
16         flag=false;
17         for(int j=1;j<loc1;j++)
18         {
19             if(a[j-1]>a[j])
20             {
21                 m=a[j-1];
22                 a[j-1]=a[j];
23                 a[j]=m;
24                 loc=j;
25                 flag=true;
26             }
27         }
28         loc1=loc;
29         if(!flag)
30             break;
31     }
32     for(int i=0;i<10;i++)
33         printf("%d
",a[i]);
34     printf("
");
35     return 0;
36 }

View Code

选择排序：

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕

步骤：

在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
以此类推，直到所有元素均排序完毕。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <math.h>
 4 
 5 int main()
 6 {
 7     int a[10];
 8     for(int i=0;i<10;i++)
 9         a[i]=random()/10000;
10     int m;
11     int min;
12     for(int i=0;i<10;i++)
13     {
14         min=i;
15         for(int j=i+1;j<10;j++)
16         {
17             if(a[j]<a[min])
18                 min=j;
19         }
20         m=a[min];
21         a[min]=a[i];
22         a[i]=m;
23     }
24     for(int i=0;i<10;i++)
25         printf("%d
",a[i]);
26     printf("
");
27     return 0;
28 }

View Code

插入排序：

冒泡排序算法的运作如下：

比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <math.h>
 4 
 5 int main()
 6 {
 7     int a[10];
 8     for(int i=0;i<10;i++)
 9         a[i]=random()/10000;
10     int m=0,index=0;
11     for(int i=1;i<10;i++)
12     {
13         if(a[i]<a[i-1])
14         {
15             m=a[i];
16             index=i;
17             for(int j=i-1;j>=0;j--)
18             {
19                 if(a[j]>m)
20                 {
21                     a[j+1]=a[j];
22                     index=j;
23                 }
24                 else
25                     break;
26             }
27             a[index]=m;
28         }
29     }
30     for(int i=0;i<10;i++)
31         printf("%d
",a[i]);
32     return 0;
33 }

View Code

希尔排序：

介绍：

希尔排序，也称递减增量排序算法，实质是分组插入排序。由 Donald Shell 于1959年提出。希尔排序是非稳定排序算法。

希尔排序的基本思想是：将数组列在一个表中并对列分别进行插入排序，重复这过程，不过每次用更长的列（步长更长了，列数更少了）来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法，算法本身还是使用数组进行排序。

例如，假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我们以步长为5开始进行排序，我们可以通过将这列表放在有5列的表中来更好地描述算法，这样他们就应该看起来是这样：

13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10

然后我们对每列进行排序：

10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45

将上述四行数字，依序接在一起时我们得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]。这时10已经移至正确位置了，然后再以3为步长进行排序：

排序之后变为：

最后以1步长进行排序（此时就是简单的插入排序了）。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <math.h>
 4 
 5 
 6 int a[10];
 7 void shell_sort(int arr[],int len)
 8 {
 9     int gap,i,j,temp;
10     for(gap=len>>1;gap>=0;gap>>1)
11         for(i=gap;i<len;i++)
12         {
13             temp=arr[i];
14             for(j=i-gap;j>=0 && a[j]>temp;j-=gap)
15                 a[j+gap]=a[j];
16             a[j+gap]=temp;
17         }
18 }
19 
20 int main()
21 {
22     for(int i=0;i<10;i++)
23         a[i]=random()/10000;
24     shell_sort(a,10);
25     for(int i=0;i<10;i++)
26         printf("%d
",a[i]);
27     return 0;
28 }

View Code

归并排序递归版：

递归法

原理如下（假设序列共有n个元素）：

将序列每相邻两个数字进行归并操作，形成 $floor(n/2)$ 个序列，排序后每个序列包含两个元素
将上述序列再次归并，形成 $floor(n/4)$ 个序列，每个序列包含四个元素
重复步骤2，直到所有元素排序完毕

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <math.h>
 4 
 5 
 6 int a[10];
 7 void merge_sort_recursive(int arr[],int reg[],int start,int end)
 8 {
 9     if(start>=end)
10         return;
11     int len=end-start,mid=(len>>1)+start;
12     int start1=start,end1=mid;
13     int start2=mid+1,end2=end;
14     merge_sort_recursive(arr,reg,start1,end1);
15     merge_sort_recursive(arr,reg,start2,end2);
16     int k=start;
17     while(start1<=end1 && start2<=end2)
18         reg[k++]=arr[start1]<arr[start2]?arr[start1++]:arr[start2++];
19     while(start1<=end1)
20         reg[k++]=arr[start1++];
21     while(start2<=end2)
22         reg[k++]=arr[start2++];
23     for(k=start;k<=end;k++)
24         arr[k]=reg[k];
25 }
26 
27 void merge_sort(int arr[],const int len)
28 {
29     int reg[len];
30     merge_sort_recursive(arr,reg,0,len-1);
31 }
32 int main()
33 {
34     for(int i=0;i<10;i++)
35         a[i]=random()/10000;
36     merge_sort(a,10);
37     for(int i=0;i<10;i++)
38         printf("%d
",a[i]);
39     return 0;
40 }

View Code

归并排序迭代版：

迭代法

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
设定两个指针，最初位置分别为两个已经排序序列的起始位置
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
重复步骤3直到某一指针到达序列尾
将另一序列剩下的所有元素直接复制到合并序列尾

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <math.h>
 4 #include <algorithm>
 5 #include <stdlib.h>
 6 
 7 int a[10];
 8 
 9 
10 
11 int min(int x,int y)
12 {
13     return x<y?x:y;
14 }
15 
16 void merge_sort(int arr[],int len)
17 {
18     int* a=arr;
19     int* b=(int*)malloc(len*(sizeof(int*)));
20     for(int reg=1;reg<len;reg+=reg)
21     {
22         for(int start=0;start<len;start+=reg+reg)
23         {
24             int low=start,mid=min(start+reg,len),high=min(start+reg+reg,len);
25             int k=low;
26             int start1=low,end1=mid;
27             int start2=mid,end2=high;
28             while(start1 < end1 && start2 < end2)
29                 b[k++]=a[start1]<a[start2]?a[start1++]:a[start2++];
30             while(start1 < end1)
31                 b[k++]=a[start1++];
32             while(start2 < end2)
33                 b[k++]=a[start2++];
34         }
35         int* temp=a;
36         a=b;
37         b=temp;
38     }
39     if(a!=arr)
40     {
41         int i;
42         for(i=0;i<len;i++)
43             b[i]=a[i];
44         b=a;
45     }
46     free(b);
47     
48 }
49 
50 int main()
51 {
52     for(int i=0;i<10;i++)
53         a[i]=random()/10000;
54     merge_sort(a,10);
55     for(int i=0;i<10;i++)
56         printf("%d
",a[i]);
57     return 0;
58 }

View Code

快排递归版：

步骤为：

从数列中挑出一个元素，称为"基准"（pivot），
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <math.h>
 4 #include <algorithm>
 5 
 6 
 7 int a[10];
 8 
 9 void swap(int *x,int *y)
10 {
11     int t=*x;
12     *x=*y;
13     *y=t;
14 }
15 
16 void quick_sort_recursive(int arr[],int start,int end)
17 {
18     if(start>=end)
19         return;
20     int mid=a[end];
21     int left=start,right=end-1;
22     while(left<right)
23     {
24         while(a[left]<mid && left<right)
25             left++;
26         while(a[right]>=mid && left<right)
27             right--;
28         swap(&a[left],&a[right]);
29     }
30     if(a[left]>a[end])
31         swap(&a[left],&a[end]);
32     else
33         left++;
34     quick_sort_recursive(arr,start,left-1);
35     quick_sort_recursive(arr,left+1,end);
36     
37 }
38 
39 void quick_sort(int arr[],int len)
40 {
41     quick_sort_recursive(arr,0,len-1);
42 }
43 
44 int main()
45 {
46     for(int i=0;i<10;i++)
47         a[i]=random()/10000;
48     quick_sort(a,10);
49     for(int i=0;i<10;i++)
50         printf("%d
",a[i]);
51     return 0;
52 }

View Code

快排迭代版：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <math.h>
 4 #include <algorithm>
 5 
 6 
 7 int a[10];
 8 
 9 
10 typedef struct _Range
11 {
12     int start,end;
13 }Range;
14 
15 Range new_Range(int s,int e)
16 {
17     Range range;
18     range.start=s;
19     range.end=e;
20     return range;
21 }
22 
23 void swap(int *x,int *y)
24 {
25     int z;
26     z=*x;
27     *x=*y;
28     *y=z;
29 }
30 
31 void quick_sort(int arr[],int len)
32 {
33     if(len<=0)
34         return;
35     Range r[len];
36     int p=0;
37     r[p++]=new_Range(0,len-1);
38     while(p)
39     {
40         Range range=r[--p];
41         if(range.start>=range.end)
42             continue;
43         int mid=arr[range.end];
44         int left=range.start,right=range.end-1;
45         while(left < right)
46         {
47             while(arr[left]<mid && left<right)
48                 left++;
49             while(arr[right]>=mid && left<right)
50                 right--;
51             swap(&arr[left],&arr[right]);
52             if(arr[left]>=arr[range.end])
53                 swap(&arr[left],&arr[range.end]);
54             else
55                 left++;
56             r[p++]=new_Range(0,left-1);
57             r[p++]=new_Range(left+1,range.end);
58         }
59     }
60 }
61 
62 int main()
63 {
64     for(int i=0;i<10;i++)
65         a[i]=random()/10000;
66     quick_sort(a,10);
67     for(int i=0;i<10;i++)
68         printf("%d
",a[i]);
69     return 0;
70 }

View Code

堆排序：

介绍：

堆排序在 top K 问题中使用比较频繁。堆排序是采用二叉堆的数据结构来实现的，虽然实质上还是一维数组。二叉堆是一个近似完全二叉树。

二叉堆具有以下性质：

父节点的键值总是大于或等于（小于或等于）任何一个子节点的键值。
每个节点的左右子树都是一个二叉堆（都是最大堆或最小堆）。

步骤：

构造最大堆（Build_Max_Heap）：若数组下标范围为0~n，考虑到单独一个元素是大根堆，则从下标n/2开始的元素均为大根堆。于是只要从n/2-1开始，向前依次构造大根堆，这样就能保证，构造到某个节点时，它的左右子树都已经是大根堆。
堆排序（HeapSort）：由于堆是用数组模拟的。得到一个大根堆后，数组内部并不是有序的。因此需要将堆化数组有序化。思想是移除根节点，并做最大堆调整的递归运算。第一次将heap[0]与heap[n-1]交换，再对heap[0...n-2]做最大堆调整。第二次将heap[0]与heap[n-2]交换，再对heap[0...n-3]做最大堆调整。重复该操作直至heap[0]和heap[1]交换。由于每次都是将最大的数并入到后面的有序区间，故操作完后整个数组就是有序的了。
最大堆调整（Max_Heapify）：该方法是提供给上述两个过程调用的。目的是将堆的末端子节点作调整，使得子节点永远小于父节点。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <math.h>
 4 #include <algorithm>
 5 
 6 
 7 int a[10];
 8 
 9 
10 
11 void swap(int *x,int *y)
12 {
13     int z;
14     z=*x;
15     *x=*y;
16     *y=z;
17 }
18 
19 void max_heapify(int arr[],int start,int end)
20 {
21     int dad=start;
22     int son=dad*2+1;
23     while(son < end)
24     {
25         if(son+1 < end && arr[son]<arr[son+1])
26             son++;
27         if(arr[dad]>arr[son])
28             return;
29         else
30         {
31             swap(&arr[dad],&arr[son]);
32             dad=son;
33             son=dad*2+1;
34         }
35     }
36 }
37 
38 void heap_sort(int arr[],int len)
39 {
40     for(int i=len/2-1;i>=0;i--)
41         max_heapify(arr,i,len);
42     for(int i=len-1;i>=0;i--)
43     {
44         swap(&arr[0],&arr[i]);
45         max_heapify(arr,0,i);
46     }
47 }
48 
49 int main()
50 {
51     for(int i=0;i<10;i++)
52         a[i]=random()/10000;
53     heap_sort(a,10);
54     for(int i=0;i<10;i++)
55         printf("%d
",a[i]);
56     return 0;
57 }

View Code

----------------------------------------------------------------------------------------------------------------------------------------------------

总结

下面为七种经典排序算法指标对比情况：

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　本文参考：wuchong

参考资料

活在现实，做在梦里。