排序算法

#define LENGTH(array) ( (sizeof(array)) / (sizeof(array[0])) )
#define swap(a,b) do{a=a+b;b=a-b;a=a-b;}while(0) //两个数相同时 会导致结果为0

 1 /**
 2 **  直接插入排序（插入到准确的位置）  不利于二分查找 直接遍历
 3 **  时间复杂度：比较和移动和平均时间复杂度为O（n^2）  适合基本有序的序列，此时复杂度接近O（n）
 4 **  空间复杂度：O(1)
 5 **  稳定性：稳定
 6 **/
 7 void InsertSort(int a[], int n)
 8 {
 9     int i, j;
10     for (i = 2; i <=n; i++)//假设第一项已经排好，所以从第二项开始
11     {
12         if (a[i] < a[i - 1])//若此项小于 前面已经排好的最后一项（已排好的最大项）
13         {
14             a[0] = a[i];//0号位置为哨兵节点
15             for (j = i - 1; a[0] < a[j]; j--)//从后 向前查找待插入位置
16             {
17                 a[j+1] = a[j];//记录后移
18             }
19             a[j+1] = a[0];//复制到插入的位置 此时a[j]已经是小于a[0]的了
20         }
21     }
22 }

 1 /**
 2 **  插入排序（插入到准确的位置） 利用二分查找
 3 **  比较复杂度：O（nlogn）
 4 **  移动复杂度：O(n^2) 
 5 **  时间复杂度为:O（n^2） 
 6 **  稳定性：稳定
 7 **/
 8 void BInsertSort(int a[], int n)
 9 {
10     int i, j, low, high, mid;
11     for (i = 2; i <= n; i++)
12     {
13         a[0] = a[i];//哨兵元素
14         low = 1; high = i - 1;
15         while (low <= high)
16         {
17             mid = (low + high) / 2;
18             if (a[mid] > a[0])
19                 high = mid - 1;
20             else
21                 low = mid + 1;
22         }
23         for (j = i - 1; j >=high+1; j--)
24             a[j + 1] = a[j];
25         a[high + 1] = a[0];
26     }
27 }

 1 /**
 2 **  希尔排序 （缩小增量的排序）
 3 **  最坏时间复杂度：O（n^2）
 4 **  平均时间复杂度：O（n^1.3）
 5 **  空间复杂度：O（1）
 6 **  稳定性：不稳定 当相同关键字被划分到不同子表时 可能会造成不稳定
 7 **/
 8 void ShellSort(int a[], int n)
 9 {
10     //a[0] 是暂存单元 不是哨兵
11     //进行插入排序的步长是dk 而不是1
12     int i, j, dk;
13     for (dk = n / 2; dk >= 1; dk = dk / 2)//步长变化
14     {
15         for (i = dk + 1; i <= n; i++)//对已经分好组的进行插入 排序 每一组都交替进行
16         {
17             if (a[i] < a[i - dk])//若当前项小于本组前一项
18             {
19                 a[0] = a[i];//暂存在a[0]
20                 for (j = i - dk; j > 0 && a[0] < a[j]; j-=dk)//从本组已经排好序的序列中找到合适的插入位置
21                     a[j + dk] = a[j];//记录后移
22                 a[j + dk] = a[0];//插入
23             }
24         }
25     }
26 }

 1 /**
 2 **  冒泡排序（每次交换,将相邻中大的一个放在后面）
 3 **  最坏时间复杂度：O（n^2）
 4 **  平均时间复杂度：O（n^2）
 5 **  最好情况下的复杂度：O(n) 初始序列有序时
 6 **  空间复杂度：O（1）
 7 **  稳定性：稳定
 8 **/
 9 //最大的上浮
10 void BubbleSort(int a[], int n)
11 {
12     for (int i = 0; i < n - 1; i++)
13     {
14         int flag = 0;
15         for (int j = 0; j < n - 1 - i; j++)//最大的向上浮
16         {
17             if (a[j] > a[j + 1])//此处若写等号 则变成不稳定的排序
18             {
19                 swap(a[j], a[j + 1]);
20                 flag = 1;
21             }
22         }
23         if (flag == 0) return;//一整趟都未交换一次 则已排序好 退出
24     }
25 }

 1 //最小的下浮
 2 void BubbleSort_m(int a[], int n)
 3 {
 4     for (int i = 0; i < n - 1; i++)
 5     {
 6         int flag = 0;
 7         for (int j = n-1; j >i; j--)//最小的向下浮
 8         {
 9             if (a[j-1] > a[j])//此处若写等号 则变成不稳定的排序
10             {
11                 swap(a[j], a[j-1]);
12                 flag = 1;
13             }
14         }
15         if (flag == 0) return;//一整趟都未交换一次 则已排序好 退出
16     }
17 }

 1 /**
 2 **  快速排序（任取枢轴pivot，将其分为小于pivot，和大于pivot的两部分，此时pivot放在了最终的位置上）
 3 **  最坏空间复杂度O（n）
 4 **  平均空间复杂度O（logn）
 5 **  最坏时间复杂度：O（n^2）
 6 **  平均时间复杂度：O（nlogn）
 7 **  稳定性：不稳定 如若3为枢轴{3，2，2‘} 经过一趟排序后 {2‘,2，3}
 8 **/
 9 int Partition(int a[], int low, int high)//根据枢轴划分两个区间
10 {
11     int pivot = a[low];//将枢轴的值存起来
12     while (low < high)
13     {
14         while (low < high && a[high] >= pivot) --high;//若高位有比枢轴小的 结束循环
15         a[low] = a[high];//将高位比枢轴小的值放到低位上 
16         while (low < high && a[low] <= pivot) ++low;//若低位有比枢轴大的值 结束循环 
17         a[high] = a[low];//将低位比枢轴大的值放在高位上
18     }
19     a[low] = pivot;//将枢轴的值放到正确的位置上
20     return low;//返回枢轴的位置
21 }
22 void QuickSort(int a[], int low, int high)
23 {
24     if (low < high)
25     {
26         int pivotloc = Partition(a, low, high);
27         QuickSort(a, low, pivotloc - 1);//依次对两个子表进行递归排序
28         QuickSort(a, pivotloc + 1, high);
29     }
30 }

 1 /**
 2 **  选择排序（每次选最小的）
 3 **  空间复杂度O（1）
 4 **  时间复杂度：O（n^2）
 5 **  稳定性：不稳定 如若{2，2‘,1} 经过一趟排序后 {1,2‘,2}
 6 **/
 7 void SelectSort(int a[], int n)
 8 {
 9     for (int i = 0; i < n - 1; i++)
10     {
11         int min = i;
12         for (int j = i + 1; j < n; j++)
13         {
14                 if (a[j] < a[min])
15                     min = j;
16         }
17         if(min!=i)
18             swap(a[i], a[min]);
19     }
20 }

 1 /**
 2 **  堆排序（每次选最小的）
 3 **  空间复杂度O（1）
 4 **  时间复杂度：O（nlogn） 建堆时间O（n） 向下平均调整时间O（nlogn）
 5 **  稳定性：不稳定 如若{1,2，2‘} 构造初始堆时将2交换到堆顶 {2,1,2‘} 最终排序为{1,2‘,2}
 6 **/
 7 
 8 //将堆中小的节点调整至下方
 9 void AdjustDown(int a[], int k, int len)
10 {
11     a[0] = a[k];//用a[0]暂存根节点
12     int i;
13     for (i = 2 * k; i <= len; i *= 2)
14     {
15         if (i < len && a[i] < a[i + 1])//找出子数较大的一个
16             i++;
17         if (a[0] >= a[i])break;//如果根节点本来就大 无须调整
18         else//叶子节点比较大
19         {
20             a[k] = a[i];//将较大的叶子节点调整到根节点
21             k = i;//以原先未调整的较大的叶子节点的位置为根再进行调整 
22         }
23     }//for
24     a[k] = a[0];//将最初暂存的根节点的值 放到最后一个做调整的叶子节点上去
25 }
26 //建大根堆
27 void BuildMaxHeap(int a[], int len)
28 {
29     for (int i = len / 2; i > 0; i--)//从i=n/2到1 反复调整堆
30         AdjustDown(a, i, len);
31 }
32 //堆排序
33 void HeapSort(int a[], int len)
34 {
35     BuildMaxHeap(a, len);//建立大根堆
36     show(a, 1,len, "after_build_max_heap:");
37     for (int i = len; i > 1; --i)//将最后一个记录与大根堆的根节点对换
38     {
39         swap(a[1], a[i]);
40         AdjustDown(a, 1, i - 1);//对根节点向下调整，序列长度为i-1 第i项为已经排列好的最大项
41     }
42 
43 }

 1 /**
 2 **  归并排序（分治法 每次分成左右两个子序列 且左右两个子序列有序）
 3 **  空间复杂度O（n） 需要辅助数组b[]
 4 **  时间复杂度：O（nlogn）
 5 **  稳定性：稳定
 6 **/
 7 void Merge(int a[], int b[], int low, int mid, int high)
 8 {
 9     //a是原数组 b是辅助数组 low-mid；mid+1-high 各自有序 将他们合并成一个有序表存放在a中
10     int i, j, count;//count代表当前排序好的数据
11     for (int k = low; k <= high; k++)//将a中所有的数据放到b中
12         b[k] = a[k];
13     for (i = low, j = mid + 1, count = low; i <= mid && j <= high; count++)//选择两个有序组中更小的一个放在a中
14     {
15         if (b[i] < b[j])
16             a[count] = b[i++];
17         else
18             a[count] = b[j++];
19     }
20     //如下两个循环只会执行一个
21     while (i <= mid) a[count++] = b[i++];//若第一个表未检测完 复制
22     while (j <= high) a[count++] = b[j++];//若第二个表未检测完 复制
23 }
24 void MergeSort(int a[],int b[], int low, int high)
25 {
26     if (low < high)
27     {
28         int mid = (low + high) / 2;//划分子序列
29         MergeSort(a,b ,low, mid);//对左侧递归
30         MergeSort(a,b, mid + 1, high);//右侧递归
31         Merge(a, b, low, mid, high);//排序
32         //show(b, 0, high+1, "b:");
33     }
34 }