1. 直接插入排序
2. 折半插入排序
3. 冒泡排序
4. 简单选择排序
5. 希尔排序
6. 快速排序
7. 堆排序
8. 二路归并排序
// Sort.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "stdio.h"
#include "iostream"
using namespace std;
// Straight insert sort
void InsertSort(int *arr,int length);
void InsertSort2(int arr[], int length);
// Binary Insert Sort
void BinInsertSort(int arr[], int length);
// Shell Sort
void ShellSort(int *arr,int length);
// Shell Sort 2
void ShellSort2(int *arr,int length);
// Bubble Sort
void BubbleSort(int *arr,int length);
// Quick Sort
void QuickSort(int *arr, int low, int high);
// Partition
int Partition(int *arr, int low, int high);
// Simple Selection Sort
void SimpleSelectionSort(int *arr, int length);
// HeapAdjust
void HeapAdjust(int *arr, int s,int end);
// Heap Sort,小根堆
void HeapSort(int *arr,int length);
// Merge Array
void Merge(int *arr, int *arr2, int left, int mid, int right);
// Merge Sort
void MergeSort(int *arr, int *arr2, int left, int right);
int _tmain(int argc, _TCHAR* argv[])
{
int arr[]={29,5,44,28,36,42,7,5,88,9,10};
int length=sizeof(arr)/sizeof(*arr);
InsertSort(arr,length);
printf("Straight Insert Sort:\n");
printf("total number:%4d\n",length);
printf("sorted result:\n");
for (int i=0;i<length;i++)
{
printf("%5d",arr[i]);
}
cout<<endl;
// test2
int arr2[]={29,5,44,28,36,42,7,5,88,9,10};
length=sizeof(arr2)/sizeof(*arr2);
InsertSort2(arr2,length);
printf("Straight Insert Sort:\n");
printf("total number:%4d\n",length);
printf("sorted result:\n");
for (int i=0;i<length;i++)
{
printf("%5d",arr2[i]);
}
cout<<endl;
// test3
int arr3[]={29,5,44,28,36,42,7,5,88,9,10};
length=sizeof(arr3)/sizeof(*arr3);
BinInsertSort(arr3,length);
printf("Binary Insert Sort:\n");
printf("total number:%4d\n",length);
printf("sorted result:\n");
for (int i=0;i<length;i++)
{
printf("%5d",arr3[i]);
}
cout<<endl;
// test4
int arr4[]={29,5,44,28,36,42,7,5,88,9,10};
length=sizeof(arr4)/sizeof(*arr4);
ShellSort(arr4,length);
printf("Shell Sort:\n");
printf("total number:%4d\n",length);
printf("sorted result:\n");
for (int i=0;i<length;i++)
{
printf("%5d",arr4[i]);
}
cout<<endl;
// test5
int arr5[]={29,5,44,28,36,42,7,5,88,9,10};
length=sizeof(arr5)/sizeof(*arr5);
ShellSort2(arr5,length);
printf("Shell Sort 2:\n");
printf("total number:%4d\n",length);
printf("sorted result:\n");
for (int i=0;i<length;i++)
{
printf("%5d",arr5[i]);
}
cout<<endl;
// test6
int arr6[]={29,5,44,28,36,42,7,5,88,9,10};
length=sizeof(arr6)/sizeof(*arr6);
BubbleSort(arr6,length);
printf("Bubble Sort:\n");
printf("total number:%4d\n",length);
printf("sorted result:\n");
for (int i=0;i<length;i++)
{
printf("%5d",arr6[i]);
}
cout<<endl;
// test7
int arr7[]={29,5,44,28,36,42,7,5,88,9,10};
length=sizeof(arr7)/sizeof(*arr7);
QuickSort(arr7,0,length-1);
printf("Quick Sort:\n");
printf("total number:%4d\n",length);
printf("sorted result:\n");
for (int i=0;i<length;i++)
{
printf("%5d",arr7[i]);
}
cout<<endl;
// test8
int arr8[]={29,5,44,28,36,42,7,5,88,9,10};
length=sizeof(arr8)/sizeof(*arr8);
SimpleSelectionSort(arr8,length);
printf("Simple Selection Sort:\n");
printf("total number:%4d\n",length);
printf("sorted result:\n");
for (int i=0;i<length;i++)
{
printf("%5d",arr8[i]);
}
cout<<endl;
// test9, 对于堆的应用，数组arr[0]暂时不用，降低处理复杂度
int arr9[]={0,29,5,44,28,36,42,7,5,88,9,10};
length=sizeof(arr9)/sizeof(*arr9)-1;
HeapSort(arr9,length);
printf("///////////////////////////////////////////////////////////////////////\n");
printf("Heap Sort:\n");
printf("total number:%4d\n",length);
printf("sorted result:\n");
for (int i=length;i>=1;i--)
{
printf("%5d",arr9[i]);
}
cout<<endl;
// 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<length;i++)
{
printf("%5d",arr10[i]);
}
cout<<endl;
system("pause");
return 0;
}
// 由小到大排序
// Straight Insert Sort
void InsertSort(int *arr,int length)
{
for (int i=1;i<length;i++)
{
if (arr[i]<arr[i-1]) // 需要将arr[i]插入到已排序的列表中
{
int temp=arr[i];
int j=0;
for (j=i-1;j>=0;j--)
{
if (temp<arr[j])
{
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<length;i++)
{
if (arr[i]<arr[i-1]) // 需要进行插入
{
int temp=arr[i];
int j=i-1;
do
{
arr[j+1]=arr[j];
j--;
} while (j>=0&&temp<arr[j]);
arr[j+1]=temp;
}
}
}
// Binary Insert Sort
void BinInsertSort(int arr[], int length)
{
for (int i=1;i<length;i++)
{
if (arr[i]<arr[i-1]) // 需要插入到有序序列中
{
int temp=arr[i];
int low=0;
int high=i-1;
while(low<=high)
{
int mid=(low+high)/2;
if (temp<mid)
{
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<length;i++) //判断每个子序列
{
if (arr[i]<arr[i-gap]) // 需要插入到已排序的子序列
{
int temp=arr[i];
int j=0;
for (j=i-gap;j>=0;j=j-gap)
{
if (temp<arr[j])
{
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<length;i++)
{
if (arr[i]<arr[i-gap])
{
int temp=arr[i];
int j=i-gap;
do
{
arr[j+gap]=arr[j];
j=j-gap;
} while (j>=0&&temp<arr[j]);
arr[j+gap]=temp;
}
}
} while (gap>1);
}
// Bubble Sort
void BubbleSort(int *arr,int length)
{
bool exchange=false;
for (int i=0;i<length-1;i++)
{
exchange=false;
for (int j=length-1;j>=i+1;j--)
{
if (arr[j]<arr[j-1]) // 需要交换
{
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<high)
{
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<high)
{
while(low<high&&arr[high]>=pivotKey) --high;
int temp=arr[high];arr[high]=arr[low];arr[low]=temp;
while(low<high&&arr[low]<pivotKey) ++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<length;i++)
{
int index=i;
for(int j=i+1;j<length;j++)
{
if (arr[j]<arr[index])
{
index=j;
}
}
if(index!=i)
{
// exchange
int temp=arr[i];
arr[i]=arr[index];
arr[index]=temp;
}
}
}
// Heap Sort,小根堆
void HeapSort(int *arr,int length)
{
// 调整数组生成小根堆
for (int i=length/2;i>=1;i--)
{
HeapAdjust(arr,i,length);
}
for (int i=length;i>1;--i)
{
// 交换堆头的元素和最后一个
int temp=arr[1];
arr[1]=arr[i];
arr[i]=temp;
// 重新调整堆为小根堆
HeapAdjust(arr,1,i-1);
}
}
// HeapAdjust
void HeapAdjust(int *arr, int s,int end)
{
int rloc=arr[s];
for (int j=2*s;j<=end;j=j*2)
{
if (j<end&&arr[j]>arr[j+1])
{
j++; // 找到两个兄弟节点中最小的节点
}
if (!(arr[j]<rloc))
{
break;
}
arr[s]=arr[j];
s=j;
}
arr[s]=rloc;
}
// Merge Sort
void MergeSort(int *arr, int *arr2, int left, int right)
{
if (left==right)
{
arr2[left]=arr[left];
return;
}
if (left<right)
{
int mid=(left+right)/2;
MergeSort(arr,arr2,left,mid);
MergeSort(arr,arr2,mid+1,right);
Merge(arr,arr2,left,mid,right);
}
}
// Merge Array
void Merge(int *arr, int *arr2, int left, int mid, int right)
{
// 将数组保存到暂存空间中
for (int k=left;k<=right;k++)
{
arr2[k]=arr[k];
}
int s1=left;
int s2=mid+1;
int t=left;
while(s1<=mid&&s2<=right)
{
if (arr2[s1]<=arr2[s2])
{
arr[t++]=arr2[s1++];
}
else
{
arr[t++]=arr2[s2++];
}
}
while(s1<=mid) arr[t++]=arr2[s1++];
while(s2<=right) arr[t++]=arr2[s2++];
}