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 }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/607589.html