- 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 }