内部排序算法（顺序表实现，附带各算法时间效率，注释清楚明晰）
数据结构学习–内部排序算法（顺序表实现）
内部排序算法（顺序表实现，附带各算法时间效率，注释清楚明晰）
（供自己学习，记录，可参考，有错请指正，缺少基数排序）
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <math.h>
#include <iostream>
using namespace std;
#define ElemType int
#define MaxSize 11
//顺序存储下的内部排序方法，效率计算
//插入排序
void InsertSort(ElemType A[],int n){//直接插入排序
int i,j;
for(i=2;i<=n;i++){
A[0]=A[i]; //哨兵
for(j=i-1;A[0]<A[j];j--) A[j+1] = A[j];//找到位置，向后移
A[j+1] = A[0]; //插入目标位置
}
}
void Binary_InsertSort(ElemType A[],int n){//折半插入排序
int i,j;
int low,high,mid;
for(int i=2;i<=n;i++){
A[0] = A[i];
low = 1;
high = i-1;
while(low<=high){//找到插入位置 在 low = high 的那个点
mid = (low+high)/2;
if(A[mid]>A[0]) high = mid-1;
low = mid+1;
}
for(j=i-1;j>=high+1;--j){//从插入位置high（low）的后一个开始到high+1 全部向后移动一个
A[j+1] = A[j];
}
A[high+1] = A[0];//插入目标位置
}
}
//选择排序
void ChooseSort(ElemType A[],int n){//简单选择排序
int i,j;
int temp;
int minIndex; //本趟中的最小的数的下标
for(i=1;i<=n;i++){
minIndex = i;
for(j=i+1;j<=n;j++){
if(A[j]<A[minIndex]) minIndex = j;
}
temp = A[i];
A[i] = A[minIndex];
A[minIndex] = temp;
}
}
void AdjustDown(ElemType A[],int k,int len){//向下调整 算法
A[0] = A[k];//暂存本轮要调整的根
for(int i=2*k;i<=len;i*=2){
if(i<len && A[i]<A[i+1]) i++; //找到两个叶子结点中的较大值下标，返回i
if(A[0]>=A[i]) break;//如果根大于两个叶子，符合，不用筛选
else{
A[k] = A[i];//否则，将大的叶子变成根
k=i;//下轮筛选的k
}
A[k] = A[0];//根放入调整叶子位置
}
}
void BuildMaxHeap(ElemType A[],int len){ //序列建立大根堆
for(int i=len/2;i>0;i--){
AdjustDown(A,i,len);
}
}
void HeapSort(ElemType A[],int len){//堆排序--大根堆排序
BuildMaxHeap(A,len);
int temp;//用于交换每轮堆顶的最大根，输出
for(int i=len;i>0;i--){
temp = A[i]; //A[1]为最大，和i交换到排序最终位置
A[i] = A[1];
A[1] = temp;
AdjustDown(A,1,i-1);//交换后，继续向下调整
}
}
//交换排序
void BubbleSort(ElemType A[],int n){//冒泡排序
int i,j,temp;
bool flag;
for(i=1;i<=n;i++){
flag = false;//本趟是否有交换，没有，那么已经有序。
for(j=n;j>i;j--){
if(A[j-1]>A[j]){
temp = A[j]; //最小的冒泡到第一个
A[j] = A[j-1];
A[j-1] = temp;
}
}
}
}
//快速排序
int partition(int a[],int left,int right)//根据pivot分割序列,找到当前pivot值的最终位置
{
int i=left;
int j=right;
int temp=a[i];
while(i<j)
{
while(i<j && a[j]>=temp)//从后向low检索，寻找比pivot小的。如果high>=pivot,位置正确不需要移动该元素，high--；
j--;
if(i<j)
a[i]=a[j];
while(i<j && a[i]<=temp)//从前向high检索，寻找比pivot大的。如果low<=pivot,位置正确不需要移动该元素，low++；
i++;
if(i<j)
a[j]=a[i];
}
a[i]=temp;
return i;
}
void quickSort(int a[],int left,int right)//快速排序
{
int dp;
if(left<right)
{
dp=partition(a,left,right);
quickSort(a,left,dp-1);
quickSort(a,dp+1,right);
}
}
//2路归并排序
void Merge(ElemType A[],int low,int mid,int high){//合并函数，合并A[1,...,mid],A[mid+1,...,high]
int i,j,m;
ElemType B[MaxSize];
for(int k=low;k<=high;k++){ //A的从low到high全部复制到辅助空间数组B
B[k] = A[k];
}
for(i=low,j=mid+1,m=i;i<=mid && j<=high;m++){ //开始记录合并的绝对位置不变! m并不是从A的1开始，而是从low(i)开始
if(B[i]<B[j])
A[m] = B[i++];
else{
A[m] = B[j++];
}
}
while(i<=mid) A[m++] = B[i++];
while(j<=high) A[m++] = B[j++];
}
void MergeSort(ElemType A[],int low,int high){ //归并排序
if(low<high){
int mid;
mid = (low+high)/2;
MergeSort(A,low,mid);
MergeSort(A,mid+1,high);
Merge(A,low,mid,high);
}
}
/*
//基数排序MSD最高位优先算法
void FundamentalSort(ElemType A[],int n){
}
*/
int main(){
clock_t start;
clock_t end;
ElemType B[MaxSize];
ElemType D[MaxSize];
ElemType C[MaxSize];
ElemType E[MaxSize];
ElemType F[MaxSize];
ElemType H[MaxSize];
//********************给定输入数据元素(10个)：704 104 789 652 365 78 53 519 507 129,复制此序列
//********************基数排序指定序列: 895 365 593 695 659 256 236 245 888 777,复制此三位数序列 r=10 d=3 O（d(n+r)）
cout<<"===================================================="<<endl;
cout<<" 插入排序 "<<endl;
cout<<"===================================================="<<endl;
cout<<"请输入数组A待排序元素序列："<<endl;
ElemType A[MaxSize];
for(int i=1;i<=10;i++) cin>>A[i];
start = clock();
for(int k=0;k<10000000;k++){
InsertSort(A,10);}
end = clock();
for(int i=1;i<=10;i++) cout<<A[i]<<' ';
cout<<endl;
cout<<"插入排序10000000次运行时间："<<double(end-start)/CLOCKS_PER_SEC<<endl;
cout<<"===================================================="<<endl;
cout<<" 折半插入排序 "<<endl;
cout<<"===================================================="<<endl;
cout<<"请输入数组B待排序元素序列："<<endl;
for(int i=1;i<=10;i++) cin>>B[i];
start = clock();
for(int k=0;k<10000000;k++){
Binary_InsertSort(B,10);}
end = clock();
for(int i=1;i<=10;i++) cout<<B[i]<<' ';
cout<<endl;
cout<<"折半插入排序10000000次运行时间："<<double(end-start)/CLOCKS_PER_SEC<<endl;
cout<<"===================================================="<<endl;
cout<<" 选择排序 "<<endl;
cout<<"===================================================="<<endl;
cout<<"请输入数组D待排序元素序列："<<endl;
for(int i=1;i<=10;i++) cin>>D[i];
start = clock();
for(int k=0;k<10000000;k++){
ChooseSort(D,10);}
end = clock();
for(int i=1;i<=10;i++) cout<<D[i]<<' ';
cout<<endl;
cout<<"选择排序10000000次运行时间："<<double(end-start)/CLOCKS_PER_SEC<<endl;
cout<<"===================================================="<<endl;
cout<<" 冒泡排序 "<<endl;
cout<<"===================================================="<<endl;
cout<<"请输入数组C待排序元素序列："<<endl;
for(int i=1;i<=10;i++) cin>>C[i];
start = clock();
for(int k=0;k<10000000;k++){
BubbleSort(C,10);}
end = clock();
for(int i=1;i<=10;i++) cout<<C[i]<<' ';
cout<<endl;
cout<<"冒泡排序10000000次运行时间："<<double(end-start)/CLOCKS_PER_SEC<<endl;
cout<<"===================================================="<<endl;
cout<<" 归并排序（2路） "<<endl;
cout<<"===================================================="<<endl;
cout<<"请输入数组F待排序元素序列："<<endl;
for(int i=1;i<=10;i++) cin>>F[i];
start = clock();
for(int k=0;k<10000000;k++){
MergeSort(F,1,10);}
end = clock();
for(int i=1;i<=10;i++) cout<<F[i]<<' ';
cout<<endl;
cout<<"归并排序10000000次运行时间："<<double(end-start)/CLOCKS_PER_SEC<<endl;
cout<<"===================================================="<<endl;
cout<<" 堆排序 "<<endl;
cout<<"===================================================="<<endl;
cout<<"请输入数组H待排序元素序列："<<endl;
for(int i=1;i<=10;i++) cin>>H[i];
start = clock();
for(int k=0;k<10000000;k++){
HeapSort(H,10);}
end = clock();
for(int i=1;i<=10;i++) cout<<H[i]<<' ';
cout<<endl;
cout<<"堆排序10000000次运行时间："<<double(end-start)/CLOCKS_PER_SEC<<endl;
cout<<"===================================================="<<endl;
cout<<" 快速排序 "<<endl;
cout<<"===================================================="<<endl;
cout<<"请输入数组E待排序元素序列："<<endl;
for(int i=1;i<=10;i++) cin>>E[i];
start = clock();
for(int k=0;k<10000000;k++){
quickSort(E,1,10);}
end = clock();
for(int i=1;i<=10;i++) cout<<E[i]<<' ';
cout<<endl;
cout<<"快速排序10000000次运行时间："<<double(end-start)/CLOCKS_PER_SEC<<endl;
return 0;
}