[关闭]
@Jayfeather 2018-06-12T10:00:28.000000Z 字数 5085 阅读 818

排序算法

数据结构与算法分析

  1. // 排序算法.cpp: 定义控制台应用程序的入口点。
  2. //忽然发现互联网对于编程学习真的是个好东西
  3. //几乎所有的知识点都有很详细的讲解
  4. //而且大多数都是别人已经扫过雷，很少有错误的
  5. //虽然没有书本权威，但是容易理解
  6. //而且还能及时的与作者交流
  7. /*这是一个包含11个算法+选择驱动程序的学习笔记*/
  8. /*懒得写注释了，凑活着看吧~*/
  9. #include "stdafx.h"
  10. #include<stdio.h>
  11. #include<stdlib.h>
  12. void swap(int *a, int *b);
  13. void sort(int A[], int num,int K);
  14. void BubbleSort(int A[], int num);
  15. void CocktailSort(int A[], int num);
  16. void SelectionSort(int A[], int num);
  17. void InsertionSort(int A[], int num);
  18. void InsertionSortDichotomy(int A[], int num);
  19. void ShellSort(int A[], int num);
  20. void MergeSort(int A[], int num);           
  21. void merge(int A[], int left, int right, int *p);
  22. void mergearry(int A[], int left, int right, int mid, int *p);
  23. void HeapSort(int A[], int num);
  24. void Heapify(int A[], int i, int heapsize);
  25. int BuildHeap(int A[], int num);
  26. void QuickSort(int A[], int num);
  27. int Partion(int A[], int right,int left);
  28. void QuickSortcom(int A[], int right, int left);
  29. void CountingSort(int A[], int num);
  30. void LsdRadixSort(int A[], int n);
  31. int GetDigit(int x, int d);
  32. void CountingSortL(int A[], int num, int d);
  33. void InsertionSort(int A[], int left, int right);
  34. int MapToBucket(int x);
  35. void CountingSortB(int A[], int num);
  36. void BucketSort(int A[], int num);
  40. int main()
  41. {
  42.     int num = 100,K=0;
  43.     int A[100] = { 80, 9, 70, 22, 3, 63, 12, 81,
  44.         73, 41, 90, 83, 27, 71, 88, 5, 40, 18, 25
  45.         , 37, 55, 60, 93, 87, 17, 89, 99, 84, 32
  46.         , 96, 62, 98, 77, 30, 23, 35, 47, 24, 21
  47.         , 53, 95, 7, 85, 2, 65, 1, 39, 43, 76, 46
  48.         , 42, 91, 4, 26, 52, 86, 34, 54, 38, 78
  49.         , 31, 11, 66, 36, 50, 75, 16, 68, 56, 33,
  50.         48, 15, 74, 69, 49, 6, 58, 10, 29, 92, 64,
  51.         59, 28, 61, 45, 19, 14, 13, 44, 72, 94,
  52.         20, 97, 51, 67, 79, 0, 82, 8, 57 };
  53.     printf("Please insert the kind of sort you want:");
  54.     scanf_s("%d", &K);
  55.     sort(A, num,K);
  56.     for (int i = 0; i < num; i++)
  57.         printf("%d ", A[i]);
  58.     return 0;
  59. }
  60. void swap(int *a, int *b)
  61. {
  62.     if (a == b)
  63.         return;
  64.     int temp;
  65.     temp = *a;
  66.     *a = *b;
  67.     *b = temp;
  68. }
  70. void sort(int A[100], int num,int K)
  71. {
  72.     switch (K)
  73.     {
  74.     case 1:
  75.         BubbleSort(A, num);
  76.         break;
  77.     case 2:
  78.         CocktailSort(A, num);
  79.         break;
  80.     case 3:
  81.         SelectionSort(A, num);
  82.         break;
  83.     case 4:
  84.         InsertionSort(A, num);
  85.         break;
  86.     case 5:
  87.         InsertionSortDichotomy(A, num);
  88.         break;
  89.     case 6:
  90.         ShellSort(A, num);
  91.         break;
  92.     case 7:
  93.         MergeSort(A, num);
  94.         break;
  95.     case 8:
  96.         HeapSort(A, num);
  97.         break;
  98.     case 9:
  99.         QuickSort(A, num);
  100.         break;
  101.     case 10:
  102.         CountingSort(A, num);
  103.         break;
  104.     case 11:
  105.         LsdRadixSort(A, num);
  106.         break;
  107.     case 12:
  108.         BucketSort(A, num);
  109.         break;
  110.     }
  111.     return ;
  112. }
  113. void BubbleSort(int A[], int num)
  114. {
  115.     for (int i = 0; i < num;i++)
  116.     {
  117.         for (int t = 0; t < num - i-1; t++)
  118.         {
  119.             if (A[t] > A[t + 1])
  120.                 swap(&A[t], &A[t + 1]);
  121.         }
  122.     }
  123. }
  125. void CocktailSort(int A[], int num)
  126. {
  127.     int i = 0;
  128.     while(i<(num+1)/2)
  129.     {
  130.         for (int m = i; m < num - i-1; m++)
  131.         {
  132.             if (A[m] > A[m + 1])
  133.                 swap(&A[m], &A[m + 1]);
  134.         }
  135.         for (int n = num - i-1; n > i; n--)
  136.         {
  137.             if (A[n] < A[n -1])
  138.                 swap(&A[n], &A[n - 1]);
  139.         }
  140.         i++;
  141.     }
  142. }
  144. void SelectionSort(int A[], int num)
  145. {
  146.     for (int i = 0; i < num; i++)
  147.     {
  148.         int temp=i;
  149.         for (int n = i; n < num; n++)
  150.         {
  151.             if (A[n] < A[temp])
  152.                 temp = n;
  153.         } 
  154.         swap(&A[temp], &A[i]);
  155.     }
  156. }
  158. void InsertionSort(int A[], int num)
  159. {
  160.     for (int i = 1; i < num; i++)
  161.     {
  162.         int temp = A[i],n=i-1;
  163.         while(n>=0)
  164.         {
  165.             if (temp <= A[n])
  166.                 A[n + 1] = A[n];
  167.             else
  168.                 break;
  169.             n--;
  170.         }
  171.         A[n+1] = temp;
  172.     }
  173. }
  175. void InsertionSortDichotomy(int A[], int num)
  176. {
  177.     for (int i = 1; i < num; i++)
  178.     {
  179.         int left = 0, right = i - 1, mid = (left + right) / 2;
  180.         int temp = A[i];
  181.         while (left <= right)
  182.         {
  183.             if (temp < A[mid])
  184.                 right = mid - 1;
  185.             if (temp >= A[mid])
  186.                 left = mid + 1;
  187.             mid = (left + right) / 2;
  188.         }
  189.         for (int n = i - 1; n >= left; n--)
  190.         {
  191.             A[n + 1] = A[n];
  192.         }
  193.         A[left] = temp;
  194.     }
  195. }
  197. void ShellSort(int A[], int num)
  198. {
  199.     int h=0;
  200.     while (h < num / 3)
  201.     {
  202.         h = 3*h + 1;
  203.     }
  204.     while (h != 0)
  205.     {
  206.             for (int i = h; i < num; i++)
  207.             {
  208.                 int temp = A[i], n = i-h;
  209.                 while (n >= 0)
  210.                 {
  211.                     if (temp <= A[n])
  212.                         A[n + h] = A[n];
  213.                     else
  214.                         break;
  215.                     n=n-h;
  216.                 }
  217.                 A[n + h] = temp;
  218.             }
  219.         h = (h - 1) / 3;
  220.     }
  221. }
  223. void MergeSort(int A[], int num)
  224. {
  225.     int *p = new int[num];
  226.     merge(A, 0, num-1, p);
  227.     //delete[] p;
  228. }
  230. void merge(int A[], int left, int right, int *p)
  231. {
  232.     int mid = (right + left) / 2;
  233.     if ((right) == left)
  234.         return;
  235.     else
  236.     {
  237.         merge(A, left, mid, p);
  238.         merge(A, mid + 1, right, p);
  239.         mergearry(A, left, right, mid, p);
  240.     }
  241. }
  243. void mergearry(int A[], int left, int right, int mid, int *p)
  244. {
  245.     int i = left, j = mid + 1, counter = 0, m = mid, n = right, *temp = p;
  246.     while (j <=right && i <= mid)
  248.     {
  249.         if (A[i] <= A[j])
  250.         {
  251.             p[counter] = A[i];
  252.             i++;
  253.         }
  254.         else if (A[i] > A[j] )
  255.         {
  256.             p[counter] = A[j];
  257.             j++;
  258.         }
  259.         counter++;
  260.     }
  261.     while (i <= mid)
  262.     {
  263.         temp[counter++] = A[i++];
  264.     }
  265.     while (j <= right)
  266.     {
  267.         temp[counter++] = A[j++];
  268.     }
  269.     for (int n = 0; n < counter; n++)
  270.     {
  271.         A[left+n] = p[n];
  272.     }
  273. }
  275. void HeapSort(int A[], int num)
  276. {
  277.     int Heapsize = BuildHeap(A, num);
  278.     while (Heapsize > 1)
  279.     {
  280.         swap(&A[0], &A[--Heapsize]);
  281.         Heapify(A, 0, Heapsize);
  282.     }
  283. }
  285. int BuildHeap(int A[], int num)
  286. {
  287.     int Heapsize = num;
  288.     for (int i = (num - 2) / 2; i >= 0; i--)
  289.     {
  290.         Heapify(A, i, Heapsize);
  291.     }
  292.     return Heapsize;
  293. }
  295. void Heapify(int A[], int i, int Heapsize)
  296. {
  297.     int left=2*i;
  298.     int right = 2 * i + 1;
  299.     int max = i;
  300.     if (left<Heapsize&&A[left] > A[max])
  301.     {
  302.         max = left;
  303.     }
  304.     if (right<Heapsize&&A[right] > A[max])
  305.     {
  306.         max = right;
  307.     }
  308.     if (max != i)
  309.     {
  310.         swap(&A[i], &A[max]);
  311.         Heapify(A, max, Heapsize);
  312.     }
  313. }
  316. void QuickSort(int A[], int num)
  317. {
  318.     int right = num, left = 0;
  319.     QuickSortcom(A, right-1, left);
  320. }
  322. void QuickSortcom(int A[], int right, int left)
  323. {
  325.     if (left>=right)
  326.         return;
  327.     else
  328.     {
  329.         int mid = Partion(A, right, left);
  330.         QuickSortcom(A, right, mid+1);
  331.         QuickSortcom(A, mid-1, left);
  332.     }
  333. }
  335. int Partion(int A[], int right, int left)
  336. {
  337.     int index = A[right];
  338.     int tail = left;
  339.     for (int n = left; n < right; n++)
  340.     {
  342.         if (A[n] < index)
  343.         {
  344.             swap(&A[n], &A[tail]);
  345.             tail++;
  346.         }
  348.     }
  349.     swap(&A[right], &A[tail]);
  350.     return tail;
  351. }
  353. void CountingSort(int A[], int num)
  354. {
  355.     const int k = 100;
  356.     int B[k] = { 0 };
  357.     int C[100];
  358.     for (int n = 0; n < num; n++)
  359.     {
  360.         B[A[n]]++;
  361.     }
  362.     for (int n = 1; n < num; n++)
  363.     {
  364.         B[n] += B[n - 1];
  365.     }
  366.     for (int n = num-1; n > 0; n--)
  367.     {
  368.         C[--B[A[n]]] = A[n];
  369.     }
  370.     for (int n = 0; n < num; n++)
  371.     {
  372.         A[n] = B[n];
  373.     } 
  374. }
  376. void LsdRadixSort(int A[], int num)
  377. {
  378.     for (int d = 1; d <3;d++)
  379.     {
  380.         CountingSortL(A, num, d);
  381.     }
  382. }
  384. int GetDigit(int x, int d)
  385. {
  386.     int Digit[3] = { 1,1,10 };
  387.     return (x / Digit[d]) % 10;
  388. }
  390. void CountingSortL(int A[], int num, int d)
  391. {
  392.     const int k = 10;
  393.     int C[k] = { 0 };
  394.     int B[100];
  395.     for (int n = 0; n < num; n++)
  396.     {
  397.         C[GetDigit(A[n], d)]++;
  398.     }
  399.     for (int n = 1; n < k; n++)
  400.     {
  401.         C[n] += C[n - 1];
  402.     }
  403.     for (int n = num - 1; n >= 0; n--)
  404. {
  405.     B[--C[GetDigit(A[n], d)]] = A[n];
  406. }
  407.     for (int n = 0; n < num; n++)
  408.     {
  409.         A[n] = B[n];
  410.     }
  411. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注