• 排序算法总结

    目录

    1.快速排序

    理论部分

    2.归并排序

    理论部分

    3.插入排序

    理论部分

    4.冒泡排序

    理论部分

    5.选择排序

    理论部分

    6.桶排序

    347. Top K Frequent Elements (Medium)

    7.堆排序

    理论部分

    8.例子

    215. Kth Largest Element in an Array

    快速选择

    归并

    根堆

    347. Top K Frequent Elements (Medium)

     法一桶排序已经在理论部分讲过了

    堆排序加优先队列（或者就叫小根堆）

    451. Sort Characters By Frequency (Medium)

    桶排序

     75. Sort Colors (Medium)

    1.快速排序

    理论部分

    1. import java.util.Arrays;
    2.  
    3. public class QuickSort {
    4.     public static void main(String[] args) {
    5.         int[] nums={11,24,5,32,50,34,54,76};
    6.         System.out.println("快速排序前:"+ Arrays.toString(nums));
    7.         quickSort(nums,0,nums.length-1);
    8.         System.out.println("快速排序后:"+ Arrays.toString(nums));
    9.     }
    10.     public static void quickSort(int[] nums, int start, int end){
    11.         if(start>end) return;
    12.         int i,j,base;
    13.         i=start;
    14.         j=end;
    15.         base=nums[start];
    16.         while (i
    17.             while (i=base) j--;
    18.             while (i
    19.             if(i
    20.                 swap(nums,i,j);
    21.             }
    22.         }
    23.         swap(nums,start,i);
    24.         quickSort(nums,start,j-1);
    25.         quickSort(nums,j+1,end);
    26.     }
    27.     public static void swap(int[] nums,int left,int right){
    28.         int temp=nums[left];
    29.         nums[left]=nums[right];
    30.         nums[right]=temp;
    31.     }
    32. }

    快速排序(详细讲解)_梦里Coding的博客-CSDN博客_快速排序

    这个讲的非常好，建议就看这个看明白就好了

    2.归并排序

    理论部分

    这一个比较好理解：

    1. int* Merge_Sort(int arr[], int start, int end) {
    2.     //当start==end时，此时分组里只有一个元素，所以这是临界点
    3.     if (start < end) {
    4.         //分成左右两个分组，再进行递归
    5.         int mid = (start + end) / 2;
    6.         //左半边分组
    7.         Merge_Sort(arr, start, mid);
    8.         //右半边分组
    9.         Merge_Sort(arr, mid + 1, end);
    10.         //递归之后再归并归并一个大组
    11.         Merge(arr, start, mid, end);
    12.     }
    13.     return arr;
    14. }
    15.  
    16. void Merge(int arr[], int start, int mid, int end) {
    17.     //左边分组的起点i_start，终点i_end，也就是第一个有序序列
    18.     int i_start = start;
    19.     int i_end = mid;
    20.     //右边分组的起点j_start，终点j_end，也就是第二个有序序列
    21.     int j_start = mid + 1;
    22.     int j_end = end;
    23.     //额外空间初始化，数组长度为end-start+1
    24.     int *temp = new int[end - start + 1];
    25.     int len = 0;
    26.     //合并两个有序序列
    27.     while (i_start <= i_end && j_start <= j_end) {
    28.         //当arr[i_start]
    29.         if (arr[i_start] < arr[j_start]) {
    30.             temp[len] = arr[i_start];
    31.             len++;
    32.             i_start++;
    33.         }
    34.         else {
    35.             temp[len] = arr[j_start];
    36.             len++;
    37.             j_start++;
    38.         }
    39.         //temp[len++]=arr[i_start]
    40.     }
    41.  
    42.     //i这个序列还有剩余元素
    43.     while (i_start <= i_end) {
    44.         temp[len] = arr[i_start];
    45.         len++;
    46.         i_start++;
    47.     }
    48.     //j这个序列还有剩余元素
    49.     while (j_start <= j_end) {
    50.         temp[len] = arr[j_start];
    51.         len++;
    52.         j_start++;
    53.     }
    54.     //辅助空间数据覆盖到原空间
    55.     for (int i = 0; i < end - start + 1; i++) {
    56.         arr[start + i] = temp[i];
    57.     }
    58. }

    图解归并排序，带你彻底了解清楚！_程序员的时光的博客-CSDN博客_归并排序这个教程很推荐

    然后下面是简洁版的：

    1. void merge_sort(vector<int>& nums, int l, int r, vector<int>& temp) {
    2.     if (l + 1 >= r) {
    3.         return;
    4.     }
    5.     // divide
    6.     int m = l + (r - l) / 2;
    7.     merge_sort(nums, l, m, temp);
    8.     merge_sort(nums, m, r, temp);
    9.     // conquer
    10.     int p = l, q = m, i = l;
    11.     while (p < m || q < r) {
    12.         if (q >= r || (p < m && nums[p] <= nums[q])) {
    13.             temp[i++] = nums[p++];
    14.         }
    15.         else {
    16.             temp[i++] = nums[q++];
    17.         }
    18.     }
    19.     for (i = l; i < r; ++i) {
    20.         nums[i] = temp[i];
    21.     }
    22. }

    3.插入排序

    理论部分

    1. void insertion_sort(vector<int> &nums, int n) {
    2.     for (int i = 0; i < n; ++i) {
    3.     for (int j = i; j > 0 && nums[j] < nums[j-1]; --j) {
    4.         swap(nums[j], nums[j-1]);
    5. } } }

    4.冒泡排序

    理论部分

    1. public class BubbleSort implements IArraySort {
    2.  
    3.     @Override
    4.     public int[] sort(int[] sourceArray) throws Exception {
    5.         // 对 arr 进行拷贝，不改变参数内容
    6.         int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
    7.  
    8.         for (int i = 1; i < arr.length; i++) {
    9.             // 设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已经完成。
    10.             boolean flag = true;
    11.  
    12.             for (int j = 0; j < arr.length - i; j++) {
    13.                 if (arr[j] > arr[j + 1]) {
    14.                     int tmp = arr[j];
    15.                     arr[j] = arr[j + 1];
    16.                     arr[j + 1] = tmp;
    17.  
    18.                     flag = false;
    19.                 }
    20.             }
    21.  
    22.             if (flag) {
    23.                 break;
    24.             }
    25.         }
    26.         return arr;
    27.     }
    28. }

    c++的是这样：

    1. void bubble_sort(vector<int>& nums, int n) {
    2.     bool swapped;
    3.     for (int i = 1; i < n; ++i) {
    4.         swapped = false;
    5.         for (int j = 1; j < n - i + 1; ++j) {
    6.             if (nums[j] < nums[j - 1]) {
    7.                 swap(nums[j], nums[j - 1]);
    8.                 swapped = true;
    9.             }
    10.         }
    11.         if (!swapped) {
    12.             break;
    13.         }
    14.     }
    15. }

    5.选择排序

    理论部分

    1. function selectionSort(arr) {
    2.     var len = arr.length;
    3.     var minIndex, temp;
    4.     for (var i = 0; i < len - 1; i++) {
    5.         minIndex = i;
    6.         for (var j = i + 1; j < len; j++) {
    7.             if (arr[j] < arr[minIndex]) {     // 寻找最小的数
    8.                 minIndex = j;                 // 将最小数的索引保存
    9.             }
    10.         }
    11.         temp = arr[i];
    12.         arr[i] = arr[minIndex];
    13.         arr[minIndex] = temp;
    14.     }
    15.     return arr;
    16. }

    6.桶排序

    347. Top K Frequent Elements (Medium)

    用例子说明理论，关键难点在于一个嵌套装桶

    题解
            顾名思义，桶排序的意思是为每个值设立一个桶，桶内记录这个值出现的次数（或其它属 性），然后对桶进行排序。针对样例来说， 我们先通过桶排序得到四个桶 [1,2,3,4]，它们的值分别 为 [4,2,1,1]，表示每个数字出现的次数。
            
            紧接着，我们对桶的频次进行排序，前 k 大个桶即是前 k 个频繁的数。这里我们可以使用各种 排序算法，甚至可以再进行一次桶排序，把每个旧桶根据频次放在不同的新桶内。针对样例来说， 因为目前最大的频次是 4 ， 我们建立 [1,2,3,4] 四个新桶，它们分别放入的旧桶为 [[3,4],[2],[],[1]]， 表示不同数字出现的频率。最后，我们从后往前遍历，直到找到 k 个旧桶。 
    1. vector<int> topKFrequent1(vector<int>& nums, int k) {
    2. 	unordered_map<int, int> counts;
    3. 	int max_count = 0;
    4. 	for (const int& num : nums) {
    5. 		max_count = max(max_count, ++counts[num]);//通过key找到value
    6. 		//这里其实是map添加元素方法里面的赋值添加，没有通过insert
    7. 	}
    8. 	vectorint>> buckets(max_count + 1);
    9. 	for (const auto& p : counts) {
    10. 		buckets[p.second].push_back(p.first);
    11. 	}
    12. 	vector<int> ans;
    13. 	for (int i = max_count; i >= 0 && ans.size() < k; --i) {
    14. 		for (const int& num : buckets[i]) {
    15. 			ans.push_back(num);
    16. 			if (ans.size() == k) {
    17. 				break;
    18. 			}
    19. 		}
    20. 	}
    21. 	return ans;
    22. }

    注意，桶排序的话，map要先学会。

    7.堆排序

    理论部分

    建议阅读大话数据结构，上面讲的非常清楚，由于本文章用于笔记而非教程，就不赘述了。

    下面是大根堆的代码：

    1. //大根堆
    2. void HeapAdjust(vector<int>& r, int s, int m)
    3. {
    4.     int temp, j;
    5.     temp = r[s];
    6.     for (j = 2 * s; j <= m; j *= 2) /* 沿关键字较大的孩子结点向下筛选 */
    7.     {
    8.         if (j < m && r[j] < r[j + 1])
    9.             ++j; /* j为关键字中较大的记录的下标 */
    10.         if (temp >= r[j])
    11.             break; /* rc应插入在位置s上 */
    12.         r[s] = r[j];
    13.         s = j;
    14.     }
    15.     r[s] = temp; /* 插入 */
    16. }
    17.  
    18.  
    19. void swap(vector<int>& r, int i, int j) {
    20.     r[i] = r[i] ^ r[j];
    21.     r[j] = r[i] ^ r[j];
    22.     r[i] = r[i] ^ r[j];
    23. }
    24.  
    25. void HeapSort(vector<int>& r, int len)
    26. {
    27.     int i;
    28.     for (i = len / 2; i >= 0; i--) /*  把L中的r构建成一个大顶堆 */
    29.         HeapAdjust(r, i, len);
    30.  
    31.     for (i = len; i > 0; i--)
    32.     {
    33.         swap(r, 0, i); /* 将堆顶记录和当前未经排序子序列的最后一个记录交换 */
    34.         HeapAdjust(r, 0, i - 1); /*  将L->r[1..i-1]重新调整为大顶堆 */
    35.     }
    36. }

    小根堆要是不用stl会很麻烦.......

    8.例子

    215. Kth Largest Element in an Array

     这个问题有多个方法，一个一个说：

    快速选择

    快速选择一般用于求解 k-th Element 问题，可以在 O(n) 时间复杂度，O(1) 空间复杂度完成求 解工作。快速选择的实现和快速排序相似，不过只需要找到第 k 大的枢（ pivot ）即可，不需要对其左右再进行排序。与快速排序一样，快速选择一般需要先打乱数组，否则最坏情况下时间复杂度为 O (n2)，我们这里为了方便省略掉了打乱的步骤。

     需要好好体会。

    1.  
    2. void swap(vector<int>&nums, int left, int right) {
    3.     int temp = nums[left];
    4.     nums[left] = nums[right];
    5.     nums[right] = temp;
    6. }
    7. void quickSort(vector<int>& nums, int start, int end) {
    8.     if (start > end) return;
    9.     int i, j, base;
    10.     i = start;
    11.     j = end;
    12.     base = nums[start];
    13.     while (i < j) {
    14.         //一定要先动j
    15.         while (i < j && nums[j] >= base) j--;
    16.         while (i < j && nums[i] <= base) i++;
    17.         if (i < j) {
    18.             swap(nums, i, j);
    19.         }
    20.     }
    21.     swap(nums, start, i);
    22.     quickSort(nums, start, j - 1);
    23.     quickSort(nums, j + 1, end);
    24. }
    25.  
    26. int findKthLargest2(vector<int>& nums, int k) {
    27.     quickSort(nums, 0, nums.size() - 1);
    28.     int i = nums.size() - 1;
    29.     while (k > 1) {
    30.         i--;
    31.         k--;
    32.     }
    33.     return nums[i];
    34.  
    35. }

    归并

    1.  
    2. void Merge_Sort(vector<int>& arr, int start, int end) {
    3.     //当start==end时，此时分组里只有一个元素，所以这是临界点
    4.     if (start < end) {
    5.         //分成左右两个分组，再进行递归
    6.         int mid = (start + end) / 2;
    7.         //左半边分组
    8.         Merge_Sort(arr, start, mid);
    9.         //右半边分组
    10.         Merge_Sort(arr, mid + 1, end);
    11.         //递归之后再归并归并一个大组
    12.         Merge(arr, start, mid, end);
    13.     }
    14.  
    15. }
    16.  
    17. void Merge(vector<int>& arr, int start, int mid, int end) {
    18.     //左边分组的起点i_start，终点i_end，也就是第一个有序序列
    19.     int i_start = start;
    20.     int i_end = mid;
    21.     //右边分组的起点j_start，终点j_end，也就是第二个有序序列
    22.     int j_start = mid + 1;
    23.     int j_end = end;
    24.     //额外空间初始化，数组长度为end-start+1
    25.     int* temp = new int[end - start + 1];
    26.     int len = 0;
    27.     //合并两个有序序列
    28.     while (i_start <= i_end && j_start <= j_end) {
    29.         //当arr[i_start]
    30.         if (arr[i_start] < arr[j_start]) {
    31.             temp[len] = arr[i_start];
    32.             len++;
    33.             i_start++;
    34.         }
    35.         else {
    36.             temp[len] = arr[j_start];
    37.             len++;
    38.             j_start++;
    39.         }
    40.         //!!!!!!!!!!!!!!!!!!!!!!!!!!    temp[len++]=arr[i_start]
    41.     }
    42.  
    43.     //i这个序列还有剩余元素
    44.     while (i_start <= i_end) {
    45.         temp[len] = arr[i_start];
    46.         len++;
    47.         i_start++;
    48.     }
    49.     //j这个序列还有剩余元素
    50.     while (j_start <= j_end) {
    51.         temp[len] = arr[j_start];
    52.         len++;
    53.         j_start++;
    54.     }
    55.     //辅助空间数据覆盖到原空间
    56.     for (int i = 0; i < end - start + 1; i++) {
    57.         arr[start + i] = temp[i];
    58.     }
    59. }
    60.  
    61. int findKthLargest1(vector<int>& nums, int k) {
    62.     Merge_Sort(nums, 0, nums.size() - 1);
    63.     int i = nums.size() - 1;
    64.     while (k > 1) {
    65.         i--;
    66.         k--;
    67.     }
    68.     return nums[i];
    69.  
    70. }

    根堆

    1. void HeapAdjust(vector<int>& r, int s, int m)
    2. {
    3.     int temp, j;
    4.     temp = r[s];
    5.     for (j = 2 * s; j <= m; j *= 2) /* 沿关键字较大的孩子结点向下筛选 */
    6.     {
    7.         if (j < m && r[j] < r[j + 1])
    8.             ++j; /* j为关键字中较大的记录的下标 */
    9.         if (temp >= r[j])
    10.             break; /* rc应插入在位置s上 */
    11.         r[s] = r[j];
    12.         s = j;
    13.     }
    14.     r[s] = temp; /* 插入 */
    15. }
    16.  
    17.  
    18. void swap(vector<int>& r, int i, int j) {
    19.     r[i] = r[i] ^ r[j];
    20.     r[j] = r[i] ^ r[j];
    21.     r[i] = r[i] ^ r[j];
    22. }
    23.  
    24. void HeapSort(vector<int>& r, int len)
    25. {
    26.     int i;
    27.     for (i = len / 2; i >= 0; i--) /*  把L中的r构建成一个大顶堆 */
    28.         HeapAdjust(r, i, len);
    29.  
    30.     for (i = len; i > 0; i--)
    31.     {
    32.         swap(r, 0, i); /* 将堆顶记录和当前未经排序子序列的最后一个记录交换 */
    33.         HeapAdjust(r, 0, i - 1); /*  将L->r[1..i-1]重新调整为大顶堆 */
    34.     }
    35. }
    36.  
    37.  
    38. int findKthLargest(vector<int>& nums, int k) {
    39.     HeapSort(nums, nums.size() - 1);
    40.     int i = nums.size() - 1;
    41.     while (k > 1) {
    42.         i--;
    43.         k--;
    44.     }
    45.  
    46.     return nums[i];
    47.  
    48. }

    347. Top K Frequent Elements (Medium)

     法一桶排序已经在理论部分讲过了

    我们来看法二：

    堆排序加优先队列（或者就叫小根堆，利用stl的priority_queue）

    其实前k个高频或者低频的问题就要想到用根堆
    这里就需要小根堆
    求前 k 大，用小根堆，求前 k 小，用大根堆。
    map是很合适的一种存储结构，key就是元素，value就是出现次数

    思路是这样：
    我们之前不是学了把一个数组构建成堆嘛
    那在这里我们先把数据存入map然后其实关键是对value进行排序，然后输出对应的key
    不过，既然要求前k个高频的，我们不需要对map所有的元素进行排序（nlogn），我们只要维护前K个高频


    说到这里是不是有想法了，我们以大根堆为例，用完全二叉树来编号，我们限制编号最大为k
    我们对map进行遍历，每次来判断是不是要加入堆里面，要加就加进去，并且要维持大根堆的形状


    这里为什么要用小根堆？大根堆不是顶点最大吗，好像要用大顶堆
    定义一个大小为k的大顶堆，在每次移动更新大顶堆的时候，每次弹出都把最大的元素弹出去了(加入元素都加在末尾)


     一般弹出都是弹出顶


    所以我们要用小顶堆，因为要统计最大前k个元素，只有小顶堆每次将最小的元素弹出，最后小顶堆里积累的才是前k个最大元素。


    这样时间复杂度就是n*logk,因为二叉树只维护k个元素


    然后这里还有一个现成的数据结构，叫优先队列  priority_queue

     时间复杂度：O(nlogk)
     空间复杂度：O(n)


    topk （前k大）用小根堆，维护堆大小不超过 k 即可。每次压入堆前和堆顶元素比较，如果比堆顶元素还小，直接扔掉，否则压入堆。检查堆大小是否超过 k，如果超过，弹出堆顶。复杂度是 nlogk 避免使用大根堆，因为你得把所有元素压入堆，复杂度是 nlogn，而且还浪费内存。如果是海量元素，那就挂了。
    [注意]

    求前 k 大，用小根堆，求前 k 小，用大根堆。

    1. class Solution {
    2. public:
    3.     // 小顶堆
    4.     class mycomparison {
    5.     public:
    6.         bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
    7.             return lhs.second > rhs.second;/*注意这个是大于，这和底层实现有关，反正就是用到了查一查就好，没必要记*/
    8.         }
    9.     };
    10.     vector<int> topKFrequent(vector<int>& nums, int k) {
    11.         // 要统计元素出现频率
    12.         unordered_map<int, int> map; // map
    13.         for (int i = 0; i < nums.size(); i++) {
    14.             map[nums[i]]++;
    15.         }
    16.  
    17.         // 对频率排序
    18.         // 定义一个小顶堆，大小为k
    19.         priority_queueint, int>, vectorint, int>>, mycomparison> pri_que;
    20.  
    21.         // 用固定大小为k的小顶堆，扫面所有频率的数值
    22.         for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {
    23.             pri_que.push(*it);
    24.             if (pri_que.size() > k) { // 如果堆的大小大于了K，则队列弹出，保证堆的大小一直为k
    25.                 pri_que.pop();
    26.             }
    27.         }
    28.  
    29.         // 找出前K个高频元素，因为小顶堆先弹出的是最小的，所以倒叙来输出到数组
    30.         vector<int> result(k);
    31.         for (int i = k - 1; i >= 0; i--) {
    32.             result[i] = pri_que.top().first;
    33.             pri_que.pop();
    34.         }
    35.         return result;
    36.  
    37.     }
    38. };

    451. Sort Characters By Frequency (Medium)

    桶排序

    体会叠加

    1. string frequencySort(string s) {
    2. 	unordered_map  <char, int> count;
    3. 	int max_count = 0;
    4. 	for (int i = 0; i < s.size(); ++i) {
    5. 		++count[s[i]];
    6. 		max_count = max(max_count, count[s[i]]);
    7. 	}
    8. 	//这种叠加的，真的要体会
    9. 	vector buckets(max_count );
    10. 	for (const auto& p : count) {
    11. 		int temp = p.second;
    12. 		while (temp > 0) {
    13. 			buckets[p.second - 1].push_back(p.first);
    14. 			--temp;
    15. 		}
    16. 	}
    17.  
    18. 	string ans;
    19. 	for (int i = max_count - 1; i >= 0; --i) {
    20. 		ans.append(buckets[i]);
    21. 	}
    22.  
    23.  
    24. 	return ans;
    25. }

     75. Sort Colors (Medium)

    特色是只有012,所以可以写出更简洁的代码

    先看通用的快速排序：

    1.  
    2. void swap(vector<int>& nums, int left, int right) {
    3.     int temp = nums[left];
    4.     nums[left] = nums[right];
    5.     nums[right] = temp;
    6. }
    7. void quickSort(vector<int>& nums, int start, int end) {
    8.     if (start > end) return;
    9.     int i, j, base;
    10.     i = start;
    11.     j = end;
    12.     base = nums[start];
    13.     while (i < j) {
    14.         //一定要先动j
    15.         while (i < j && nums[j] >= base) j--;
    16.         while (i < j && nums[i] <= base) i++;
    17.         if (i < j) {
    18.             swap(nums, i, j);
    19.         }
    20.     }
    21.     swap(nums, start, i);
    22.     quickSort(nums, start, j - 1);
    23.     quickSort(nums, j + 1, end);
    24. }
    25. void sortColors(vector<int>& nums) {
    26.     quickSort(nums, 0, nums.size() - 1);
    27.  
    28.  
    29. }

     更简洁的：

    1.  
    2. //扫描一遍的
    3. void sortColors2(vector<int>& nums, int len) {
    4.  
    5.     int r1 = -1;
    6.     int r2 = -1;
    7.     for (int i = 0; i < len; i++) {
    8.         if (nums[i] < 2)
    9.         {
    10.             r2++;
    11.             swap(nums, i, r2);
    12.             if (nums[r2] < 1)
    13.             {
    14.                 r1++;
    15.                 swap(nums, r1, r2);
    16.             }
    17.         }
    18.  
    19.     }
    20. }
    21. class Solution {
    22. public:
    23.     void sortColors(int nums[], int len) {
    24.         int num0 = 0, num1 = 0, num2 = 0;
    25.         for (int i = 0; i < len; i++) {
    26.             if (nums[i] == 0) {
    27.                 nums[num2++] = 2;
    28.                 nums[num1++] = 1;
    29.                 nums[num0++] = 0;
    30.             }
    31.             else if (nums[i] == 1) {
    32.                 nums[num2++] = 2;
    33.                 nums[num1++] = 1;
    34.             }
    35.             else {
    36.                 nums[num2++] = 2;
    37.             }
    38.         }
    39.     }
    40. };

    注意：还有希尔排序、基数排序等，个人认为熟练掌握以上排序已经完全足够，以后有时间会继续补充的。

  • 相关阅读:
    消息中间件
    A. Print a Pedestal (Codeforces logo?)
    LDRA Testbed(TBrun)软件单元测试_操作指南
    私有化部署自己的ChatGPT，免费开源的chatgpt-next-web搭建
    用 ZEGO Avatar 做一个虚拟人｜虚拟主播直播解决方案
    2023年【N1叉车司机】考试试卷及N1叉车司机考试技巧
    Golang goroutine MPG模式浅析
    SQL按年月创建动态表
    MySQL---表的增查改删（CRUD进阶）
    安装keras、tensorflow
  • 原文地址：https://blog.csdn.net/keepstrivingchy/article/details/126839118