排序算法

首先定义一个两个数对换的函数——swap

void swap(int *a1, int *a2)
{
    int tmp;
    tmp = *a1;
    *a1 = *a2;
    *a2 = tmp;

}

View Code

1 插入排序：有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序。

如图：

下面这个是我写的插入排序，不能算是真正意义上的插入排序。我的思想确实是把后面无序的第一个元素插入前面已经排好序的数组中，但是第11,12行的思想并不是找到合适的插入位置，而是逐个比较，无序的第一个元素和有序区的元素逐个交换。

 1 void sorting(int *a, int n)
 2 {
 3     int i, j,key;
 4     for (j = 1; j <n; j++)
 5     {
 6         key = j;
 7         for (i = j - 1; i >= 0; i--)
 8         {
 9             if (a[i]>a[key])
10             {
11                 swap(&a[i], &a[key]);
12                 key = i;
13                 
14 
15             }
16                 
17         }
18     }
19     
20 }

这是一个标准版本的插入排序：第9行表示如果有序区的元素大于key，则将该元素后移一位，直到到了有序区首位或是找到小于key的元素时，将key插入适当位置。算法是稳定的，因为两个相等元素由于不满足大于或者小于的关系而不会发生越位的插入。时间复杂度为O(n²)。

 1 void sorting(int *a, int n)
 2 {
 3     int i, j,key;
 4     for (j = 1; j <n; j++)
 5     {
 6         key = a[j];
 7         for (i = j; i >0&&a[i-1]>key; i--)
 8         {
 9             a[i] = a[i - 1];
10                 
11         }
12         a[i] = key;
13     }
14     
15 }

2 冒泡排序：它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。随着趟数的增多，每趟需要比较的次数逐渐减少。

时间复杂度：

如果序列是正序的，关键字的比较次数C和移动次数M均达到最小值，C=n-1,M=0

如果序列完全逆序，则需要经过n-1趟排序，每趟排序需要经过n-i次比较（1≤i≤n-1，分别是是n-1，n-2,...,1），每次比较需要通过移动记录三次来达到交换位置记录。

C=n(n-1)/2

M=3n(n-1)/2

因此，冒泡排序的平均时间复杂度为 O(n²)

算法稳定性：

冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，我想你是不会再无聊地把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。

 1 void sorting(int *a, int n)
 2 {
 3     int i, j;
 4     for (i = 0; i < n - 1; i++)
 5     {
 6         for (j = 1; j < n - i; j++)
 7         {
 8             if (a[j - 1]>a[j])
 9             {
10                 swap(&a[j - 1], &a[j]);
11             }
12         }
13     }
14 }

上述算法没有判断标志，需要进行二重循环，算法时间度不受序列本身顺序的限制，为：。这对（接近）正序的序列来说显然不是最优的。所以，需要设定一个判断标识，当序列已经正序了之后不再进行比较和移动，改进的算法如下：

 1 void sorting(int *a, int n)
 2 {
 3     int j;
       int i=0;
 4     bool sorted=false;
 5     while(!sorted)
 6     {
 7        sorted=true;
 8         for (j = 1; j < n - i; j++)
 9         {
10             if (a[j - 1]>a[j])
11             {
12                 swap(&a[j - 1], &a[j]);
13                 sorted=false;//当所有的元素都正序时，不会进入内循环，sorted值依然是ture，可跳出while循环
14             }
15         }
16         n--；
17     }
18 }

3 选择排序：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。算法复杂度为：O(n²)。是一个不稳定的算法，比如：序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了。

 1 void sorting(int *a, int n)
 2 {
 3     int i, j,min;
 4     for ( i = 0; i < n-1; i++)
 5     {
 6         min = i;
 7         for ( j = i+1; j < n; j++)
 8         {
 9             if (a[min] > a[j])
10                 min = j;
11         }
12         swap(&a[i], &a[min]);
13 
14     }
15 }

4 快速排序

快速排序是对冒泡排序的一种本质改进。它的基本思想是通过一趟扫描后，使得排序序列的长度能大幅度地减少。在冒泡排序中，一次扫描只能确保最大数值的数移到正确位置，而待排序序列的长度可能只减少1。快速排序通过一趟扫描，就能确保某个数（以它为基准点吧）的左边各数都比它小，右边各数都比它大。然后又用同样的方法处理它左右两边的数，直到基准点的左右只有一个元素为止。

设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。

算法不稳定，时间复杂度最理想 O(nlogn) 最差时间O(n^2)

 1 void　QuickSort(int　a[],int　numsize)/*a是整形数组，numsize是元素个数*/
 2 {
 3 　int　i=0,j=numsize-1;
 4 　int　val=a[0];/*指定参考值val大小*/
 5 　if(numsize>1)/*确保数组长度至少为2，否则无需排序*/
 6 　{
 7 　while(i<j)/*循环结束条件*/
 8 　{
 9 　/*从后向前搜索比val小的元素，找到后填到a[i]中并跳出循环*/
10 　for(;j>i;j--)
11 　if(a[j]<val)
12 　{
13 　a[i++]=a[j]; /*先插入再自增*/
14 　break;
15 　}
16 　/*从前往后搜索比val大的元素，找到后填到a[j]中并跳出循环*/
17 　for(;i<j;i++)
18 　if(a[i]>val)
19 　{
20 　a[j--]=a[i];
21 　break;
22 　}
23 　}
24 　a[i]=val;/*将保存在val中的数放到a[i]中*/
25 　QuickSort(a,i);/*递归，对前i个数排序*/
26 　QuickSort(a+i+1,numsize-i-1);/*对i+2到numsize这numsize-1-i个数排序*/
27 　}
28 }