常用的7种排序算法——以leetcode75.SortColors为例

前面&＃xff1a;链表的排序参考&＃xff1a;链表的排序-冒泡&＃xff0c;简单选择&＃xff0c;插入排序&＃xff0c;归并&＃xff0c;快排——以leetcode148. Sort List为例子。本文讲数组的排序。

Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note: You are not suppose to use the library&＃39;s sort function for this problem.

Example:

Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

Follow up:

• A rather straight forward solution is a two-pass algorithm using counting sort.
  First, iterate the array counting number of 0&＃39;s, 1&＃39;s, and 2&＃39;s, then overwrite array with total number of 0&＃39;s, then 1&＃39;s and followed by 2&＃39;s.
• Could you come up with a one-pass algorithm using only constant space?

二、解答

本题目实际上考察的而是排序问题&＃xff0c;这里总结了7种排序算法的C&＃43;&＃43;经典写法。7种排序算法分别是冒泡&＃xff0c;简单选择&＃xff0c;直接插入&＃xff0c;希尔排序&＃xff0c;堆排序、归并排序、快排。

分别的复杂度&＃xff0c;及稳定性为下表所示

稳定性记忆方法&＃xff1a;一起&＃xff08;希&＃xff09;快&＃xff08;快排&＃xff09;选&＃xff08;简单选择&＃xff09;排队&＃xff08;堆&＃xff09;

下面是各种排序的代码

class Solution {
public:void sortColors(vector& nums) {//method 1; Bubble sort O(n2) 最好O(n)最差O&＃xff08;n2&＃xff09; beat 22%
// if(nums.empty())
// return;
// int n &＃61; nums.size();
// bool flag &＃61; true;// for(int i &＃61; 0; i !&＃61; n && flag; &＃43;&＃43;i)
// {
// flag &＃61; false;
// for(int j &＃61; n - 2; j >&＃61; i; --j)//从后面开始循环
// {
// if(nums[j] // {
// swap(nums[j &＃43; 1], nums[j]);
// flag &＃61; true;
// }// }
// }
// return;//METHOD 2&＃xff1a;simple select sort 简单选择排序 找到最小的再进行交换 O(n2) 最好O(n2) 最差O&＃xff08;n2&＃xff09; beat 99%
// if(nums.empty())
// return;
// int n &＃61; nums.size();
// for(int i &＃61; 0; i !&＃61; n; &＃43;&＃43;i)
// {
// int min &＃61; i;
// for(int j &＃61; i &＃43; 1; j !&＃61; n; &＃43;&＃43;j)
// {
// if(nums[j] // min &＃61; j;
// }
// if(i !&＃61; min)
// swap(nums[i], nums[min]);
// }// return;//MEHTOD 3: straight insertion sort 直接插入 O(n2) 最好O(n)最差O&＃xff08;n2&＃xff09;beat 100%// if(nums.empty())// return ;// for(int i &＃61; 1; i !&＃61; nums.size(); &＃43;&＃43;i)// {// if(nums[i] temp; --j)// nums[j &＃43; 1] &＃61; nums[j];// nums[j &＃43; 1] &＃61; temp;//切记此时的时候是nums[j&＃43; 1]没有用了&＃xff0c;要覆盖也是覆盖j&＃43; 1// }// }// return ;//method 4&＃xff1a; shell sort O(nlogn) - O(n2) 最好O&＃xff08;n1.3&＃xff09;最差O&＃xff08;n2&＃xff09; beat 100%
// if(nums.empty())
// return;
// int n &＃61; nums.size();
// int increment &＃61; n;
// do
// {
// increment &＃61; increment / 3 &＃43; 1;
// for(int i &＃61; increment; i // {
// if(nums[i] // {
// int temp &＃61; nums[i];
// int j &＃61; i - increment;//初始化
// for(j &＃61; i - increment; j >&＃61; 0 && nums[j] > temp; j -&＃61; increment)
// nums[j &＃43; increment] &＃61; nums[j];
// nums[j&＃43; increment] &＃61; temp;
// }
// }
// }
// while(increment > 1);// return;//Method 5: Heap sort 三个都是O(nlogn)//简单选择的扩展&＃xff0c;每次记录比较的结果 升序一般是大顶堆&＃xff0c; 降序一般是小顶堆 堆一定是完全二叉树
// if(nums.empty())
// return;
// int n &＃61; nums.size();
// // create
// for(int i &＃61; n / 2 - 1; i >&＃61; 0; --i)//最大的具有子孩子的节点是n/2-1
// {
// adjustHeap(nums, i, n);
// }// //adjust
// for(int i &＃61; n - 1; i >&＃61; 0; --i)
// {
// swap(nums[0], nums[i]);//将堆顶元素与末尾元素交换
// adjustHeap(nums, 0, i);//调整剩下的i长度的元素为大顶堆
// }// return; //METHOD 6: merge sort 三个都是O(nlogn) 辅助空间是O&＃xff08;n&＃xff09;稳定// if(nums.empty())// return;// int n &＃61; nums.size();// vector res(n);//辅助空间// merge_sort(nums, res, 0, n -1);// return;//METHOD 7: quick sort 最好 平均O(nlogn) 最坏是O&＃xff08;n2&＃xff09;if(nums.empty())return;int n &＃61; nums.size();quick_sort(nums, 0, n-1);return;}//the subfunction of Heap sort: adjust heap function
// void adjustHeap(vector & nums, int i, int len)
// {
// int temp &＃61; nums[i];
// for(int k &＃61; 2 * i &＃43; 1; k // {
// if(k &＃43; 1 // &＃43;&＃43;k;
// if(nums[k] > temp)//如果子节点大于父节点&＃xff0c;将子节点值赋给父节点&＃xff08;不用进行交换&＃xff09;
// {
// nums[i] &＃61; nums[k];
// i &＃61; k; //i记录了每次的最大值 节点的索引, 后面只需要交换一次&＃xff0c;将最小值temp给索引i的节点
// }// }
// nums[i] &＃61; temp;//直交换一次&＃xff0c;最小值赋值给上面原最大值 节点的索引处
// return;
// } //the subfunction 1 of merge sort: divide-agency
// void merge_sort(vector & nums, vector & res, int left, int right)
// {
// if(left // {
// int mid &＃61; left &＃43; (right - left) /2;
// //divide
// merge_sort(nums, res, left, mid);
// merge_sort(nums, res, mid &＃43; 1, right);
// //agency
// merge(nums, res, left, right, mid);
// }// }//the subfunction 2 of merge sort: merge sort function
// void merge(vector & nums, vector & res, int left, int right, int mid)
// {
// int i &＃61; left;//左半边序列的起始元素索引[left, mid]
// int j &＃61; mid&＃43; 1;//右半边序列的起始元素索引[mid&＃43;1, right]
// int t &＃61; 0;//中间变量,每次t从0开始存储
// while(i <&＃61; mid && j <&＃61; right)
// {
// res[t&＃43;&＃43;] &＃61; (nums[i] <&＃61; nums[j]) ? nums[i&＃43;&＃43;] : nums[j&＃43;&＃43;];
// }
// while(i <&＃61; mid || j <&＃61; right)
// {
// res[t&＃43;&＃43;] &＃61; (i <&＃61; mid) ? nums[i&＃43;&＃43;] : nums[j&＃43;&＃43;];//注意i &＃61;&＃61; mid 说明nums[i]用完了&＃xff0c;此时应该赋值nums[j&＃43;&＃43;]
// }
// //将排好序的序列赋回原值
// t &＃61; 0;
// while(left <&＃61; right)//left递增到right停止
// {
// nums[left&＃43;&＃43;] &＃61; res[t&＃43;&＃43;];//中间变量,每次t从0开始赋值给left
// }
// return;// }//the subfunction of quick sort: quick sortvoid quick_sort(vector & nums, int left, int right){int pivot;if(left & nums, int left, int right){//int mid &＃61; left &＃43; (right - left) / 2;int pivot &＃61; nums[left];while(left !&＃61; right){while(left !&＃61; right && nums[right] >&＃61; pivot)--right;nums[left] &＃61; nums[right];while(left !&＃61; right && nums[left] <&＃61; pivot)&＃43;&＃43;left;nums[right] &＃61; nums[left];}nums[left] &＃61; pivot;return left;}
};