常用排序算法 总结 (六)

// test10
int arr10[]={29,5,44,28,36,42,7,5,88,9,10};
length=sizeof(arr10)/sizeof(*arr10);
int * arr10_2=new int[length];
MergeSort(arr10,arr10_2,0,length-1);
printf("///////////////////////////////////////////////////////////////////////\n");
printf("Merge Sort:\n");
printf("total number:%4d\n",length);
printf("sorted result:\n");
for (int i=0;i {
printf("%5d",arr10[i]);
}
cout<

system("pause");
return 0;
}

// 由小到大排序
// Straight Insert Sort
void InsertSort(int *arr,int length)
{
for (int i=1;i {
if (arr[i] {
int temp=arr[i];
int j=0;
for (j=i-1;j>=0;j--)
{
if (temp {
arr[j+1]=arr[j];
}
else
{
break;
}
}
arr[j+1]=temp;
}
}
}

// Straight Insert Sort 2
void InsertSort2(int arr[], int length)
{
for (int i=1;i {
if (arr[i] {
int temp=arr[i];
int j=i-1;
do
{
arr[j+1]=arr[j];
j--;
} while (j>=0&&temp arr[j+1]=temp;
}
}
}

// Binary Insert Sort
void BinInsertSort(int arr[], int length)
{
for (int i=1;i {
if (arr[i] {
int temp=arr[i];
int low=0;
int high=i-1;
while(low<=high)
{
int mid=(low+high)/2;
if (temp {
high=mid-1;
}
else if (temp>mid)
{
low=mid+1;
}
else
{
low=mid+1;
break;
}
}
for(int j=i-1;j>=low;j--)
{
arr[j+1]=arr[j];
}
arr[low]=temp;
}
}
}

// Shell Sort
void ShellSort(int *arr,int length)
{
// Shell Sort
int gap=length; // 初始化子序列的间隔
do
{
gap=gap/3+1;
for (int i=0+gap;i {
if (arr[i] {
int temp=arr[i];
int j=0;
for (j=i-gap;j>=0;j=j-gap)
{
if (temp {
arr[j+gap]=arr[j];
}
else
{
break;
}
}
arr[j+gap]=temp;
}
}
} while (gap>1);
}

// Shell Sort 2
void ShellSort2(int *arr,int length)
{
int gap=length;
do
{
gap=gap/3+1;
for (int i=0+gap;i {
if (arr[i] {
int temp=arr[i];
int j=i-gap;
do
{
arr[j+gap]=arr[j];
j=j-gap;
} while (j>=0&&temp arr[j+gap]=temp;
}
}
} while (gap>1);
}

// Bubble Sort
void BubbleSort(int *arr,int length)
{
bool exchange=false;
for (int i=0;i {
exchange=false;
for (int j=length-1;j>=i+1;j--)
{
if (arr[j] {
exchange=true;
int temp=arr[j-1];
arr[j-1]=arr[j];
arr[j]=temp;
}
}
if (exchange==false)
{
return;
}
}
}

// Quick Sort
void QuickSort(int *arr, int low, int high)
{
if (low {
int pivocLoc=Partition(arr,low,high);
QuickSort(arr,low,pivocLoc-1);
QuickSort(arr,pivocLoc+1,high);
}
}

// Partition
int Partition(int *arr, int low, int high)
{
int pivotKey=arr[low]; // 记录枢轴
while(low {
while(low=pivotKey) --high;
int temp=arr[high];arr[high]=arr[low];arr[low]=temp;
while(low temp=arr[high];arr[high]=arr[low];arr[low]=temp;
}
return low;
}

// Simple Selection Sort
void SimpleSelectionSort(int *arr, int length)
{
//
for (int i=0;i {
int index=i;
for(int j=i+1;j {
if (arr[j] {
index=j;
}
}
if(index!=i)
{
// exchange