void print(int a[], int n ,int i){
cout<<i <<": ";
for(int j= 0; j<n; j++){
cout<<a[j] <<" ";
}
cout<<endl;
}
void swap(int& a, int& b)
{
int temp = a;
a = b;
b = temp;
}
//直接插入排序
void StraightInsertSort(int a[], int num)
{
cout<<"StraightInsertSort "<<endl;
for (int i=1; i<num; i++)
{
if (a[i] < a[i-1]) //插入元素小于前一个元素，向前插入
{
int x = a[i];
int k = i-1;
a[i] = a[i-1];
while (x < a[k]) //依次向后移动
{
a[k+1] = a[k];
k--;
}
a[k+1] = x;
}
print(a, num, i);
}
}
//希尔排序，改进直接插入排序
void ShellInsertSort(int a[], int num, int dk)
{
cout<<"dk= "<<dk<<endl;
for (int i=dk; i<num; i++)
{
if (a[i] < a[i-dk])
{
int x = a[i];
int k = i - dk;
a[i] = a[k];
while (x < a[k])
{
a[k+dk] = a[k];
k -= dk;
}
a[k+dk] = x;
}
print(a, num, i);
}
}
void ShellSort(int a[], int num)
{
cout<<"ShellInsertSort "<<endl;
int dk = num/2;
while (dk >= 1)
{
ShellInsertSort(a, num, dk);
dk /= 2;
}
}
//简单选择排序
void SimpleSelectSort(int a[], int num)
{
for (int i=0; i<num; i++)
{
int minNum = a[i];
int pos = -1;
for (int k=i+1; k<num; k++)
{
if (minNum > a[k])
{
minNum = a[k];
pos = k;
}
}
if (pos != -1)
{
a[pos] = a[i];
a[i] = minNum;
}
print(a, num, i);
}
}
//双向选择排序
void SelectionExSort(int a[], int num)
{
for (int i=1; i<=num/2; i++)
{
int maxPos = i-1;
int minPos = num-i;
for (int k=i+1; k<num-i; k++)
{
if (a[maxPos] < a[k])
{
maxPos = k;
}
if (a[minPos] > a[k])
{
minPos = k;
}
}
if (a[minPos] < a[i-1])
{
swap(a[minPos], a[i-1]);
}
if (a[maxPos] > a[num-i])
{
swap(a[maxPos], a[num-i]);
}
print(a, num, i);
}
}
//冒泡排序
void BubbleSort(int a[], int num)
{
for (int i=0; i<num; i++)
{
for (int k=0; k<num-1-i; k++)
{
if (a[k] > a[k+1])
{
swap(a[k], a[k+1]);
}
}
print(a, 10, i);
}
}
//简化冒泡排序，如果之后有序，不在排列
void BubbleSort_1(int a[], int num)
{
int endPos = num-1;
int i = 0;
while (endPos > 0)
{
int pos = 0;
for (int k=0; k<endPos; k++)
{
if (a[k] > a[k+1])
{
pos = k;
swap(a[k], a[k+1]);
}
}
endPos = pos;
print(a, 10, i++);
}
}
//双向冒泡排序
void BubbleSort_2(int a[], int num)
{
int lowPos = 0;
int highPos = num-1;
int k;
int i = 0;
while (lowPos < highPos)
{
for (k=lowPos; k<highPos; k++)
{
if (a[k] > a[k+1])
{
swap(a[k], a[k+1]);
}
}
highPos--;
print(a, 10, i);
for (k=highPos; k>lowPos; k--)
{
if (a[k] < a[k-1])
{
swap(a[k], a[k-1]);
}
}
lowPos++;
print(a, 10, i++);
}
}
static int i = 0;
//快速排序
void QuickSort(int a[], int low, int high)
{
if (low >= high)
{
return;
}
int first = low;
int last = high;
int key = a[low];
while (first < last)
{
while (first < last && a[last] >= key)
{
last--;
}
a[first] = a[last];
while (first < last && a[first] <= key)
{
first++;
}
a[last] = a[first];
}
a[first] = key;
print(a, 10, i++);
QuickSort(a, low, first-1);
QuickSort(a, first+1, high);
}
//归并排序
void Merge(int sourceArr[],int tempArr[],int startIndex,int midIndex,int endIndex)
{
int i = startIndex,j=midIndex+1,k = startIndex;
while(i!=midIndex+1 && j!=endIndex+1)
{
if(sourceArr[i]<sourceArr[j])
tempArr[k++] = sourceArr[i++];
else
tempArr[k++] = sourceArr[j++];
}
while(i!=midIndex+1)
tempArr[k++] = sourceArr[i++];
while(j!=endIndex+1)
tempArr[k++] = sourceArr[j++];
for(i=startIndex;i<=endIndex;i++)
sourceArr[i] = tempArr[i];
}
//内部使用递归
void MergeSort(int sourceArr[],int tempArr[],int startIndex,int endIndex)
{
int midIndex;
if(startIndex<endIndex)
{
midIndex=(startIndex+endIndex)/2;
MergeSort(sourceArr,tempArr,startIndex,midIndex);
MergeSort(sourceArr,tempArr,midIndex+1,endIndex);
Merge(sourceArr,tempArr,startIndex,midIndex,endIndex);
}
print(sourceArr, 10, i++);
}