基礎排序演算法

  1 #include <iostream>
  2 /*****
  3 *
  4 *實現一些基礎的排序演算法
  5 *
  6 *****/
  7 void display(int R[], int n)
  8 {
  9     for (int i = 0; i < n; ++i)
 10     {
 11         std::cout << R[i] << " ";
 12     }
 13     std::cout << std::endl;
 14 }
 15 
 16 /* 1 冒泡排序 */
 17 void BubbleSort(int R[], int n)
 18 {
 19     int i, j;
 20     int tmp;
 21     for (i = 0;i < n - 1; ++i)
 22     {
 23         //從後面開始找，將最小的冒到第一個位子
 24         for(j = n - 1; j > i; --j)
 25         {
 26             if (R[j] < R[j - 1])
 27             {
 28                 tmp = R[j];
 29                 R[j] = R[j - 1];
 30                 R[j - 1] = tmp;
 31             }
 32         }
 33     }
 34 }
 35 
 36 /* 2 直接插入排序 從第二個位子開始排好序 */
 37 void InsertSort(int R[], int n)
 38 {
 39     int i , j;
 40     int tmp;
 41     for (i = 1; i < n; ++i)
 42     {
 43         j = i - 1;
 44         tmp = R[i];//可以不用這個變數 相當於拿一個數 然後向後找一個合適的位子
 45         while(j >= 0 && tmp < R[j])
 46         {
 47             R[j + 1] = R[j];
 48             j--;
 49         }
 50         R[j+1] = tmp;
 51     }
 52 }
 53 
 54 /* 3 選擇排序 從第一個位子開始選擇一個最小的數放在這裡 */
 55 void SelectSort(int R[], int n)
 56 {
 57     int i, j, k;
 58     int tmp;
 59     for (i = 0; i < n; ++i)
 60     {
 61         k = i;
 62         //i 前面的（比i小的）都已經排好序了
 63         for (j = i + 1; j < n; ++j)
 64         {
 65             if (R[k] > R[j])
 66             {
 67                 k = j;
 68             }
 69         }
 70 
 71         //找到最小的數所在的位子k 將這個數放在i所在的位子
 72         if (k != i)
 73         {
 74             tmp = R[i];
 75             R[i] = R[k];
 76             R[k] = tmp;
 77         }
 78     }
 79 }
 80 
 81 /* 4 快速排序 從數組的第一個數開始作為基準數，將整個數組的左邊放比它小的，右邊放比它大的*/
 82 void QuickSort(int R[], int s, int t)
 83 {
 84     int i = s , j = t;
 85     int tmp;
 86     if(s < t)
 87     {
 88         tmp = R[s];
 89         while(i != j)
 90         {
 91             //右邊找一個比基準數小的
 92             while(i < j && tmp <= R[j])
 93             {
 94                 j--;
 95             }
 96             // 找到了就賦到左邊
 97             if (i < j)
 98             {
 99                  R[i++] = R[j];
100             }
101             //左邊找一個比基準數大的
102             while(i < j && tmp >= R[i])
103             {
104                 i++;
105             }
106             //找到了就賦到右邊
107             if (i < j)
108             {
109                 R[j--] = R[i];
110             }
111         }
112         R[i] = tmp;
113         //一個基準數結束之後 左邊和右邊再排序
114         QuickSort(R, s, i - 1);
115         QuickSort(R, i + 1, t);
116 
117     }
118 
119 }
120 
121 
122 int main()
123 {
124     int r[10] = {3, 4, 5, 2, 1, 0, 9, 8 ,7, 6};
125     QuickSort(r, 0, 10);
126     display(r, 10);
127 }