c/c++语言开发共享基础排序算法

  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 }