排序算法

  1 /*
  2  * 排序：冒泡排序
  3  * 平均时间复杂度：O(n*n)
  4  * 最坏时间复杂度：O(n*n)
  5  * 空间复杂度：O(1)
  6  * 稳定性：稳定
  7  * 思路:它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。
  8  *      走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
  9  *      每一次i的循环就是找到最小的那个数
 10  * */
 11 void SortAlgorithm::bubbleSort(vector<int> A) {
 12     int size = A.size();
 13     if (size < 2) {
 14         return;
 15     }
 16     for (int i = 0; i < size - 1; i++) {
 17         for (int j = i + 1; j < size; j++) {
 18             if (A[i] > A[j]) {
 19                 swap(A[i], A[j]);
 20             }
 21         }
 22     }
 23 }
 24 
 25 /*
 26  * 排序：选择排序
 27  * 平均时间复杂度：O(n*n)
 28  * 最坏时间复杂度：O(n*n)
 29  * 空间复杂度：O(1)
 30  * 稳定性：不稳定  由于每次会有交换所以会导致不稳定  eg：4 2 4 1 第一次交换是第一个4和1交换 导致不稳定
 31  * 思路:每一次找到最小的那个数  交换当前没有排序的最前面的位置
 32  * */
 33 void SortAlgorithm::selectionSort(vector<int> A) {
 34     int size = A.size();
 35     if (size < 2) {
 36         return;
 37     }
 38     for (int i = 0; i < size - 1; i++) {
 39         int indexMin = i;
 40         for (int j = i + 1; j < size; j++) {
 41             if (A[j] < A[indexMin]) {
 42                 indexMin = j;
 43             }
 44         }
 45         if (i != indexMin) {
 46             swap(A[indexMin], A[i]);
 47         }
 48     }
 49 }
 50 
 51 /*
 52  * 排序：直接插入排序
 53  * 平均时间复杂度：O(n*n)
 54  * 最坏时间复杂度：O(n*n)
 55  * 空间复杂度：O(1)
 56  * 稳定性：稳定
 57  * 思路: 插入排序就是后面的元素当成新的元素,插入已经排序好的序列里面
 58  * */
 59 void SortAlgorithm::straightInsertionSort(vector<int> A) {
 60     int size = A.size();
 61     if (size < 2) {
 62         return;
 63     }
 64     for (int i = 1; i < size; i++) {
 65         if (A[i - 1] > A[i]) {
 66             int temp = A[i], j;
 67             for (j = i - 1; j >= 0 && A[j] > temp; j--) {
 68                 A[j + 1] = A[j];
 69             }
 70             A[j + 1] = temp;
 71         }
 72     }
 73 }
 74 
 75 /*
 76  * 排序：快速排序
 77  * 平均时间复杂度：O(nlogn)
 78  * 最坏时间复杂度：O(n*n)
 79  * 空间复杂度：0(logn)
 80  * 稳定性：不稳定
 81  * 思路：通过哨兵的操作 把数组分成 左右两个 把数组的左边的第一个数当成基数  然后从右边开始 右边找比基数小的数 左边找比基数大的数
 82  *      在left<right的时候找到了就交换位置 最后交换左右碰面和基数的位置  就保证了基数左面的数一定小于基数  基数右边的数一定大于基数
 83  *      然后递归 基数左边的  基数右边
 84  * */
 85 void SortAlgorithm::quickSort(int a[], int low, int high) {
 86     if (low >= high) {
 87         return;
 88     }
 89     int first = low;
 90     int last = high;
 91     int key = a[first];
 92 
 93     while (first < last) {
 94         while (first < last && a[last] >= key) {
 95             --last;
 96         }
 97         a[first] = a[last];
 98         while (first < last && a[first] <= key) {
 99             ++first;
100         }
101         a[last] = a[first];
102     }
103     a[first] = key;
104     quickSort(a, low, first - 1);
105     quickSort(a, first + 1, high);
106 }