算法之排序

排序算法中有非常经典的算法思想蕴含其中，本篇主要实现了几种经典的排序算法，希望常常回看，彻底牢记！

• 定义：将数组中的数按照升序或降序进行排列
• 时间复杂度：
  • \(O(NlogN)\)：快速排序、归并排序、堆排序等
  • \(O(N^2)\)：冒泡排序，插入排序等

测试样例：

1 0 30 22 21 21 28 8 6 4 -1

快速排序

思路参考：https://wiki.jikexueyuan.com/project/easy-learn-algorithm/fast-sort.html

代码参考：http://runoob.com/w3cnote/quick-sort-2.html

• 解题思路：将问题分解为以下三步

  1. 找到基准点pivot，用partition()分区函数，使得基准点左侧均小于基准点，右侧均大于等于基准点【从小到大排序】
  2. 递归完成pivot左侧的数组排序
  3. 递归完成pivot右侧的数组排序

• 代码：

  #include<iostream>
  #include<vector>
  
  using namespace std;
  
  int Partation(vector<int> & A, int start, int end)
  {
  	int value = A[start];
  	while(start < end)
  	{
  		while(start < end && A[end] >= value)
  		{
  			--end;
  		}
  		A[start] = A[end];
  		while(start < end && A[start] <= value)
  		{
  			++start;
  		}
  		A[end] = A[start];
  	}
  	A[start] = value;
  	return start;
  }
  
  void quickSort(vector<int> & A, int start, int end) // notice that it is the & of A
  {
  	if(start < end)
  	{
  		int pivot = Partation(A, start, end);
  		quickSort(A, start, pivot - 1);
  		quickSort(A, pivot + 1, end);
  	}
  	return;
  }
  
  int main()
  {
  	vector<int> A;
  	int a = 0;
  	while(cin >> a && a != -1)
  	{
  		A.push_back(a);
  	}
  	cout << "Ascending Order:" << endl;
      
  	quickSort(A, 0, A.size()-1);
      
  	for(int i=0; i<A.size(); ++i)
  	{
  		cout << A[i] << " ";
  	}
  	cout << endl;
  	
  	system("pause");
  	return 0;
  }

• 复杂度分析：快排的平均时间复杂度是\(O(NlogN)\)，但是最坏时间复杂度是\(O(N^2)\)，具体证明后续补充。空间复杂度\(O(N)\)

• 稳定性：不稳定的

---

归并排序

思路参考：https://blog.csdn.net/dugudaibo/article/details/79508198

递归法代码参考：https://www.runoob.com/w3cnote/merge-sort.html

迭代法代码参考：https://blog.csdn.net/dugudaibo/article/details/79508198

• 递归解题思路：将问题分解为以下三步

  1. 按照中点，将序列分为前后两部分，并递归下去
  2. 每部分只有1个元素时（此时不同部分都是按照增序或降序排列的），开始按照规则合并，规则为将两个part进行归并，使得总顺序递增或递减（两个指针）

• 代码：

  #include<iostream>
  #include<vector>
  
  # define MAX 0x7fffffff // notice that there is no "="
  
  using namespace std;
  
  int Merge(vector<int> & A, int start, int mid, int end)
  {
      vector<int> a1(A.begin() + start, A.begin() + mid + 1);
      vector<int> a2(A.begin() + mid + 1, A.begin() + end + 1);
      a1.insert(a1.end(), MAX);
      a2.insert(a2.end(), MAX);
      int index1 = 0, index2 = 0;
      for(int i=start; i<=end; ++i) // notice that i could 'equal to end'
      {
          if(a1[index1] < a2[index2])
          {
              A[i] = a1[index1];
              ++index1;
          }
          else
          {
              A[i] = a2[index2];
              ++index2;
          }
      }
  }
  
  void mergeSort(vector<int> & A, int start, int end) // notice that it is the & of A
  {
  	if(start < end)
  	{
  		int mid = start/2 + end/2;
  		mergeSort(A, start, mid);
  		mergeSort(A, mid + 1, end);
     		Merge(A, start, mid, end);
  	}
  	return;
  }
  
  int main()
  {
  	vector<int> A;
  	int a = 0;
  	while(cin >> a && a != -1)
  	{
  		A.push_back(a);
  	}
  	
  	cout << "Ascending Order:" << endl;
  	mergeSort(A, 0, A.size()-1);
  	for(int i=0; i<A.size(); ++i)
  	{
  		cout << A[i] << " ";
  	}
  	cout << endl;
  	
  	system("pause");
  	return 0;
  }

• 复杂度分析：快排的平均时间复杂度是\(O(NlogN)\)，但是最坏时间复杂度是\(O(N^2)\)，具体证明后续补充。空间复杂度\(O(N)\)

• 稳定性：不稳定的

---