基于比较、渐进最优、最好情况只能降到O(nlogn)：
Insert sort 插入排序 O(N^2) 稳定
void Insert_sort(int a[],int n) //插入排序
{
int i,j,temp;
for(i=1;i<n;i++)//把起始点看作是排好的序列，从第2个点开始向该序列插入
{
temp=a[i];//把待插入的点保存
for(j=i-1;temp<a[j]&&j>=0;j--)//将待插入点与已排好的序列的尾部开始比较
//稳定的插入排序，不使用<=而是用<
{
a[j+1]=a[j];
}//循环执行完还有一个减一
a[j+1]=temp;
}
}
Shell sort希尔排序 O(N)~O(N^2)平均O(N^1.5) 不稳定
Void Shell_sort(int a[],int n) //希尔排序
{
int i,j,k,temp;
for(k=(n/2);k>=1;k=k/2) //间隔从n/2 到1
{
for(i=k;i<n;i++) //一定间隔下对各组进行插入排序,从已排好序列尾部出发
{
temp=a[i];
for(j=i-k;temp<a[j]&&j>=0;j=j-k) //将待插入点与已排好的序列的尾部开始比较
{
a[j+k]=a[j];
}
a[j+k]=temp;
}
}
}
Select sort选择排序 O(N^2) 不稳定
void Select_sort(int a[],int n)
{
int i,j,k,temp;
for(i=0;i<n-1;i++)
{
k=i; ///将a[0]作为初始元素
for(j=i+1;j<n;j++) //从第2到第n-1中找最小的
if(a[j]<a[k])
k=j; k存放后面标号最小的
if(k!=i) //若找到的最小元素比a[i]小，二者交换
{
temp=a[k];
a[k]=a[i];
a[i]=temp;
}
}
}
Heap sort 堆排序 O(N*logN) 不稳定
方式一：
void heap_adjust( int R[], int low, int high)
{
int i=low, j=2*I; //R[j]是R[i]的左孩子
int temp=R[i];
while(j<=high)
{
if(j<high&&R[j]<R[j+1])
j++; -----j的位置放的是值大的孩子
if(temp<R[j]) { R[i]=R[j]; ---将R[j]调整到双亲的位置 i=j; j=2*i; } else break; ----双亲大，不需调整 ｝ R[i]=temp; } void heap_sort( int R[], int n) { int i; int temp; for(i=n/2;i>=1;i--) ---循环建立初始堆
heap_adjust(R,i,n);
for(i=n;i>=2;i--)
{
temp=R[1];
R[1]=R[i]
R[i]=temp;
heap_adjust(R,1,i-1); ---调整R[1]
}
}
方式二：
template
void adjust(T* arr,int sign,int len){
T temp = arr[sign];
//每一次循环都更新该父节点为根的完全二叉树最大堆
for (int i = sign * 2 + 1; i < len; i = i * 2 + 1){
//不断往下深入，比较两个子节点
if (i + 1 < len && arr[i + 1] > arr[i])
i++;
//判断较大的子节点 大于父节点
if (arr[i] > temp){
arr[sign] = arr[i];
sign = i;
}
}
arr[sign] = temp;
}
template
void sort(T* arr,int length){
//1.从所有非叶子节点 构建初始大顶堆
for (int i = length / 2 - 1; i >= 0; i--){
自下而上的下滤
adjust(arr, i, length);
}
//
for (int i = length - 1; i; i--){
//2.交换最大堆 和 相对的最后一个元素
swap(arr, i, 0);
//3.重新调整堆结构
adjust(arr, 0, i);
}
}
Bubble sort冒泡排序 O(N^2) 稳定
void bubble_sort(int a[],int n)
{
int i,j,temp;
for(i=1;i<n;i++) //做n-1次循环，每次交换的次数递减
for(j=0;j<n-i;j++) //第1次做n-1次交换，第2次做n-2次交换...,第n-1次做1次交换 //每次末尾都会增加一个选取的最大元素，不用参与下次排序 if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
Quick sort 快速排序 O(N*logN)-O(N^2) 平均为O(N*logN) 基点用头中尾三点中间的一个 不稳定
void quick_sort(int arr[], int left, int right)
{
if (left > right)
return;
int j = partition(arr, left, right);//按照j划分
quick_sort(arr, left, j - 1);
quick_sort(arr, j + 1, right);
}
方式一：
void partition(a[],int low,int high)
{
int temp;
temp=a[low];
while(low<high)
{
while(low<high&&a[high]>=temp)
high=high-1;
if(low<high)
{
a[low]=a[high];
low=low+1;
}
while(low<high&&a[low]<=temp)
low=low+1;
if(low<high)
{
a[high]=a[low];
high=high-1;
}
}
a[low]=temp;
return low;
}
方式二：
int partition(int arr[], int left, int right) //找基点,划分
{
int i = left + 1 ;
int j = right;
int temp = arr[left];//以最左边为基准
while(i <= j)
{
while (arr[i] < temp) i++; while (arr[j] > temp )
j--;
if (i < j)
swap(arr[i++], arr[j--]);
else i++;
}
swap(arr[j], arr[left]);//把左点基准放到中间位置
return j;
}
Merge sort 归并排序 O(N*logN) 稳定
方式一：
int *temp = new int[n];//在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
调用方法：merge_sort (arr,0,n-1,temp);
void merge_sort(int arr[],int left,int right,int temp[])
{//分是用递归完成的
if(left<right)
{
int mid = (left+right)/2;
merge_sort (arr,left,mid,temp);//左边归并排序，使得左子序列有序
merge_sort (arr,mid+1,right,temp);//右边归并排序，使得右子序列有序
merge(arr,left,mid,right,temp);//将两个有序子数组合并操作
}
}
void merge(int arr[],int left,int mid,int right,int temp[])
{
int i = left;//左序列指针
int j = mid+1;//右序列指针
int t = 0;//临时数组指针
while (i<=mid && j<=right)
{
if(arr[i]<=arr[j])
{
temp[t] = arr[i]; t++;i++;
}
else
{
temp[t] = arr[j]; t++;j++;
}
}
while(i<=mid){//将左边剩余元素填充进temp中
temp[t] = arr[i]; t++;i++;
}
while(j<=right){//将右序列剩余元素填充进temp中
temp[t] = arr[j]; t++;j++;
}
t = 0;
//将temp中的元素全部拷贝到原数组中
while(left <= right)
{
arr[left] = temp[t]; left++;t++;
}
}
方式二（vector向量）：
void merge(vector&arr, int start, int mid, int end)
{//左右部分归并
vector tmp;//辅助数组
int i = start;
int j = mid+1;
while (i <= mid&&j <= end)
{
if (arr[i] <= arr[j])
tmp.push_back(arr[i++]);
else
tmp.push_back(arr[j++]);
}//左边和右边肯定有一边到头了，不可能同时，因为每次只移动一边
while(i <= mid)
tmp.push_back(arr[i++]);
while (j <= end)
tmp.push_back(arr[j++]);
//将排好序的辅助数组赋值给原始数组
for (int i = 0; i < tmp.size(); i++)
arr[start + i] = tmp[i];
}
void mergeSort(vector&arr, int start, int end)
{
if (arr.empty()||start >= end)
return;
//将数组一分为二
int mid = (end + start) / 2;
先将左半部分排好序，再将右半部分排好序
mergeSort(arr, start, mid);
mergeSort(arr, mid+1, end);
//左右部分归并
merge(arr, start, mid, end);
for (int i = 0; i < arr.size(); i++)
cout << arr[i]<<" ";
}
相关内容：
数据结构复习笔记与一些总结：https://4r7.com/archives/907
基于比较、渐进最优的排序算法(插入、希尔、选择、堆、冒泡、快速、归并排序实现)：https://4r7.com/archives/1152
不基于比较、线性时间运行的排序算法(计数、基数、桶排序分析)和顺序、对分查找实现：https://4r7.com/archives/1165
各种算法特性与复杂度总结：https://4r7.com/archives/1174