基础排序算法

  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 }