欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

基础排序算法

程序员文章站 2022-05-30 09:28:11
一些基础算法总结一下,作为一个记录 ......
  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 }