说明
1、稳定排序：如果 a 原本在 b 的前面，且 a == b，排序之后 a 仍然在 b 的前面，则为稳定排序。
2、非稳定排序：如果 a 原本在 b 的前面，且 a == b，排序之后 a 可能不在 b 的前面，则为非稳定排序。
3、原地排序：原地排序指在排序过程中不申请多余的存储空间，只利用原来存储待排数据的存储空间进行比较和交换的数据排序。
4、非原地排序：需要利用额外的数组来辅助排序。
5、时间复杂度：一个算法执行所消耗的时间。
6、空间复杂度：运行完一个算法所需的内存大小。
性能分析
直接贴代码片：
#include<iostream>
#include<vector>
#include<stdlib.h>
#include<stack>
#include <algorithm>
using namespace std;
// 冒泡排序
void BubbleSort(int* a,int n)
{
int end = n;
int exchange = 0;
while(end)//end作为每趟排序的终止条件
{
for(int i=1;i<end;++i)
{
if(a[i-1] > a[i])
{
swap(a[i-1],a[i]);
exchange = 1;
}
}
if(0 == exchange) break;//数组本身为升序，如果一趟排序结束，并没有进行交换，那么直接跳出循环（减少循环次数，升高效率）
--end;
}
}
// 递归快排1
void quickSort1(int *a,int left,int right)
{
int i = left,j = right;
if(left>right) return;
while(i<j){
while(i<j && a[j]>=a[left])
j--;
while(i<j && a[i]<=a[left])
i++;
if(i<j){
swap(a[i],a[j]);
}
}
swap(a[i],a[left]);
quickSort1(a,left,i-1);
quickSort1(a,i+1,right);
}
// 递归快排2
void quickSort2(int *nums,int begin,int end)
{
if(begin >= end) return;
int first = begin,last = end;
int key = nums[first];
while(first<last){
while(first<last && nums[last]>=key)
last--;
if(first < last)
nums[first++] = nums[last];
while(first<last && nums[first]<=key)
first++;
if(first < last)
nums[last--] = nums[first];
}
nums[first] = key;
quickSort2(nums,begin,first-1);
quickSort2(nums,first+1,end);
}
// 非递归快排3
// 划分算法
int Partition(int *a,int low,int high)
{
if(low>=high) return -1;
int pivot = a[low];// 假设每次都以第一个元素作为枢轴值，进行一次划分：
while(low<high){
while(low<high && a[high]>=pivot)
high--;
if(low<high)
a[low++] = a[high];
while(low<high && a[low]<=pivot)
low++;
if(low<high)
a[high--] = a[low];
}
a[low] = pivot;// pivot的最终落点
return low;
}
void quickSort3(int *a,int left,int right)
{
// 利用栈来存储每次分块快排的起始点
if(left >= right) return;
stack<int> s;
int mid = Partition(a,left,right);
if(mid-1 > left){ // 确保左分区存在
// 将左分区端点入栈
s.push(left);
s.push(mid-1);
}
if(mid+1 < right){ // 确保右分区存在
// 将右分区端点入栈
s.push(mid+1);
s.push(right);
}
// 栈非空时循环获取中轴入栈
while(!s.empty()){
// 得到某分区的左右边界
int r = s.top();
s.pop();
int l = s.top();
s.pop();
mid = Partition(a,l,r);
if(mid-1 > l){
s.push(l);
s.push(mid-1);
}
if(mid+1 < r){
s.push(mid+1);
s.push(r);
}
}
}
// 插入排序
vector<int> insertSort(vector<int>& nums)
{
int n = nums.size();
for(int i=1;i<n;i++){
int flag = nums[i];
int j = i - 1;
while(j>=0 && nums[j]>flag){
nums[j+1] = nums[j];
j--;
}
nums[j+1] = flag;
}
return nums;
}
// 希尔排序（高级插入排序）
vector<int> shellSort(vector<int>& nums)
{
int n = nums.size();
int h = 1;
while(h<n/3)
h = 3*h+1;
while(h>0)
{
for(int i=h;i<n;i++)
{
int j = i-h;
int flag = nums[i];
while(j>=0 && flag<nums[j])
{
nums[j+h] = nums[j];
j = j-h;
}
nums[j+h] = flag;
}
h = h/3;
}
return nums;
}
// 选择排序
void selectSort(int *a,int n)
{
int begin = 0;
int end = n-1;
while (begin < end)
{
int min = begin,max = begin;
for(int i=begin;i<=end;++i)
{
if(a[min] > a[i])
min = i;
if(a[max] < a[i])
max = i;
}
swap(a[min],a[begin]);
if(max == begin)//如果首元素是最大的，则需要先把min 和 max的位置一换，再交换，否则经过两次交换，又回到原来的位置
max = min;
swap(a[max],a[end]);
begin++;
end--;
}
}
//堆排序
void AdjustDown(vector<int>& a, int root, int n)
{
int parent = root;
int child = parent*2+1; // 左子
while( child < n ){
if( (child+1) < n && a[child+1] > a[child] ){
++child;
}
if( a[child] > a[parent] ){
swap(a[child],a[parent]);
parent = child;
child = parent*2+1;// 到下一个子树
}
else
break;
}
}
void heapSort(vector<int>& a, int n)
{
// 找到终端节点
for( int i = n/2-1; i >=0 ; i-- )
AdjustDown(a,i,n);
int end = n - 1;
while( end > 0 ){
swap(a[0],a[end]);
AdjustDown(a,0,end);
end--;
}
}
// 归并排序
void Merge(int* a, int left, int mid, int right)
{
int *temp = new int[right - left + 1]; //申请空间存放合并数组
int st1 = left,st2 = mid + 1;
int t = 0;
while (st1 <= mid && st2 <= right)
temp[t++] = a[st1] < a[st2] ? a[st1++] : a[st2++];
while (st1 <= mid) // st2已放置完成，st1剩余
temp[t++] = a[st1++];
while (st2 <= right) // st1已放置完成，st2剩余
temp[t++] = a[st2++];
for (int j = 0; j < t; ++j) //把临时创建的数组拷贝至原数组
a[left + j] = temp[j];
delete[] temp; //销毁临时变量
}
void mergeSort(int* a, int start, int end){
if (a==NULL || start>=end)
return;
int mid = (start + end) >> 1; // 找到每个分块的中间值
mergeSort(a, start, mid);
mergeSort(a, mid + 1, end);
Merge(a, start, mid, end); // 左右合并
}
// 桶排序，用了vector<int>的快排
void bucketSort(vector<int>& shit){
int max = 0,min = 0,n = shit.size();
for(int n:shit){
if(max < n) max = n;
if(min > n) min = n;
}
int gap = (max-min) / n + 1;// 间隔
int count = (max-min) / gap +1;// 桶数
vector<int> buckets[count];
for(int n:shit){
int index = n/gap;
buckets[index].push_back(n);
}
int index = 0;
for(auto bucket:buckets){
sort(bucket.begin(),bucket.end());
for(int m:bucket){
shit[index++] = m;
}
}
}
int main()
{
int a[12] = {1,2,4,5,11,33,6,77,8,1000,5,12};
int left = 0, right = 11;
cout << "before sort:" << endl;
/* for(int val:a)
cout << val << " ";
cout << endl;
*/
vector<int> shit(a,a+12);
for(int v:shit)
cout << v << " ";
cout << endl;
//int nums = shit.size();
//BubbleSort(a,12);
//quickSort1(a,left,right);
//quickSort2(a,left,right);
//quickSort3(a,left,right);
//insertSort(shit);
//shellSort(shit);
//selectSort(a,12);
//heapSort(shit,12);
//mergeSort(a,left,right);
//bucketSort(shit);
cout << "after sort:" << endl;
for(int v:shit)
cout << v << " ";
/* for(int val:a)
cout << val << " ";
*/
cout << endl;
return 0;
}