排序术语
稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；
不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；
内排序：所有排序操作都在内存中完成；
外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；
排序算法分类
Paste_Image.png
1、冒泡排序
冒泡排序是一种较为简单的排序，通过对相邻元素进行不断的比较交换，从而将较大元素进行沉降（或上升）。
算法步骤
①从第一个元素开始，将其与其相邻元素进行比较，若不符合排序后的顺序，则交换两者位置；
②对序列中的所有相邻元素重复上述①操作，完成后则最后的元素为序列中最大值；
③除掉已排序好的元素，对剩下的元素重复①②步骤n-1次(n为待排序序列的长度）
对序列A={5,4,3,2,1}进行升序排列
Paste_Image.png
算法复杂度：对一个具有N个元素的序列来说，其循环次数为(N-1)，每次循环比较(N-i)(1<=i<=N-1)次。也就说算法复杂度为O(n2)。
完整代码
void BubbleSort(int a[],int n)
{
int i;
int j;
for(i=0;i<n-1;i++) //控制循环次数，一共n-1次
for(j=0;j<n-i-1;j++)//相邻元素进行比较交换
{
if(a[j]>a[j+1])
{
a[j]=a[j]^a[j+1];
a[j+1]=a[j]^a[j+1];
a[j]=a[j]^a[j+1];
}
}
cout<<"Bubble sort:";
Print(a,n);
}
2、直接插入排序
插入排序的基本步骤就是将一个待排序的元素插入已经排好序的序列中。其算法的基本思想就是不断的将每一个待排序的元素插入到有序的序列中，直至全部插入完为止。
算法步骤：
①序列中的第一个元素默认是有序的；
②取出下一个元素，从后向前遍历有序序列，找到插入位置；
③将有序序列中插入位置后的元素后移；
④将待插入元素插入其在有序序列中确定的位置；
⑤重复步骤②到⑤直至将待排序的元素插完为止
算法复杂度：O(n2)
void InsertSort(int a[],int n)
{
int i;
int j;
int target;
for(i=1;i<n;i++)
{
j=i;
target=a[i];
while(j>0&&target<a[j-1])//从后往前移动较好，target<a[j-1]放在while里面能减少循环次数
{
a[j]=a[j-1];
j--;
}
a[j]=target;
}
cout<<"Insertsort:";
Print(a,n);
}
3、希尔排序
希尔排序算法是插入排序的一种。也称缩小增量排序，是直接插入排序的一种高效改进版。是由DL．Shell于1959年提出的。将数组下标根据其增长分量进行分组，对组内进行直接插入算法；随着增量不断减少，组内元素也越来越多，其序列也开始基本有序；直到增量为1。
算法步骤：
①确定增量，根据增量划分子数组；
②对每个子数组进行直接插入排序；
③增量=增量/2，重复步骤①②直至增量=1；
算法复杂度：不需要大量的辅助空间，和归并排序一样容易实现。希尔排序是基于插入排序的一种算法， 在此算法基础之上增加了一个新的特性，提高了效率。希尔排序的时间复杂度与增量序列的选取有关，例如希尔增量时间复杂度为O(n²)，而Hibbard增量的希尔排序的时间复杂度为O(n3/2)，希尔排序时间复杂度的下界是n*log2n。希尔排序没有快速排序算法快 O(n(logn))，因此中等大小规模表现良好，对规模非常大的数据排序不是最优选择。但是比O(n2)复杂度的算法快得多。并且希尔排序非常容易实现，算法代码短而简单。 此外，希尔算法在最坏的情况下和平均情况下执行效率相差不是很多，与此同时快速排序在最坏的情况下执行的效率会非常差。专家们提倡，几乎任何排序工作在开始时都可以用希尔排序，若在实际使用中证明它不够快，再改成快速排序这样更高级的排序算法. 本质上讲，希尔排序算法是直接插入排序算法的一种改进，减少了其复制的次数，速度要快很多。 原因是，当n值很大时数据项每一趟排序需要的个数很少，但数据项的距离很长。当n值减小时每一趟需要和动的数据增多，此时已经接近于它们排序后的最终位置。 正是这两种情况的结合才使希尔排序效率比插入排序高很多。Shell算法的性能与所选取的分组长度序列有很大关系。只对特定的待排序记录序列，可以准确地估算关键词的比较次数和对象移动次数。想要弄清关键词比较次数和记录移动次数与增量选择之间的关系，并给出完整的数学分析，至今仍然是数学难题。
void ShellInsert(int a[],int n,int delta)
{
int i,j;
int target;
for(i=delta;i<n;i++)
{
target=a[i];
j=i-delta;
while(j>=0&&target<a[j])
{
a[j+delta]=a[j];
j=j-delta;
}
a[j+delta]=target;
}
}
void ShellSort(int a[],int n)
{
int delta;
delta=n/2;
while(delta>=1)
{
ShellInsert(a,n,delta);
delta=delta/2;
}
cout<<"Shell sort:" ;
Print(a,n);
}
4、快速排序
快速排序是一种基于分治提出的排序算法。通过选取基准数，然后将序列分为两部分，将小于基准数的元素放在一边，大于基准数的元素放在另一边。然后对着两部分重复上述操作，最终完成排序。它是处理大数据最快的算法之一。
算法步骤：
①选取基准数，遍历待排序序列
②将小于基准数的元素放在基准元素的左边，大于基准数的元素放在基准数的邮编
③分别对基准数的左右两边的序列重复步骤①②步骤
算法复杂度：O(nlgn)
Paste_Image.png
Paste_Image.png
void swap(int a[],int i,int j)
{
int temp;
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
int Partion(int a[],int left,int right)
{
int key=left;
while(left<right)
{
while(right>left&&a[right]>=a[key])
right--;
while(left<right&&a[left]<=a[key])
left++;
swap(a,left,right);
}
swap(a,left,key);
return left;
}
void QuickSort(int a[],int left,int right)
{
if(left>=right)
return;
int position;
position=Partion(a,left,right);
QuickSort(a,left,position-1);
QuickSort(a,position+1,right);
}
5、归并排序
归并排序也是一种采用分治思想的排序算法，它将待排序的序列分成很多子序列，然后再将子序列合并。在子序列合并的过程中完成序列的排序。
算法步骤：
①将长度为n的待排序序列分为两个长度都为n/2的子序列
②对这两个子序列分别进行归并排序
③将两个排序好的子序列合成完整的已排序的序列
算法复杂度：O(nlog2)
void Merge(int a[],int left,int mid,int right)
{
int size=right-left+1;
int* temp=new int[size];
int i,k,p;
i=left;
k=mid+1;
p=0;
while(i<=mid&&k<=right)
{
if(a[i]<a[k])
{
temp[p]=a[i];
i++;
}
else
{
temp[p]=a[k];
k++;
}
p++;
}
while(i<=mid)
{
temp[p]=a[i];
p++;
i++;
}
while(k<=right)
{
temp[p]=a[k];
p++;
k++;
}
for(p=0;p<size;p++)
a[left+p]=temp[p];
}
void MergeSort(int a[],int left,int right)
{
int mid;
if(left>=right)
return;
mid=(right-left)/2+left;
MergeSort(a,left,mid);
MergeSort(a,mid+1,right);
Merge(a,left,mid,right);
}
6、选择排序
选择排序是一种简单直观的排序算法。不断遍历序列找到最大值或最小值放在待排序序列的首部。
算法思想：
①选取待排序序列A中的最大值或最小值与待排序序列的最左元素A[0]进行交换，此时待排序序列为A[1...n-1]
②重复上述步骤①，直到所有元素有序
算法复杂度：O(n2):
void SelectSort(int a[],int n)
{
int i;
int j;
int MinIndex;
for(i=0;i<n;i++)
{
MinIndex=i;//每次从开始为止寻找最小值的索引，所以初始索引为开始位置
for(j=i+1;j<n;j++)
{
if(a[j]<a[MinIndex])
{
MinIndex=j;
}
}
swap(a,i,MinIndex);
}
cout<<"Selectsort:";
Print(a,n);
}
7、堆排序
堆分为大根堆和小根堆，是完全二叉树
①首先将待排序序列调整成大根堆
②将堆顶元素与无序序列中的最后一个元素交换
③然后将剩下的无序序列重复①、②步骤
算法复杂度：O(nlogn)
void HeapAdjust(int a[],int start,int end)
{
int i;
for(i=start*2+1;i<end;i=i*2+1)
{
if(i+1<end)
{
if(a[i]<a[i+1])
i=i+1;
}
if(a[start]>a[i])
break;
else
{
swap(a,start,i);
start=i;
}
}
}
void HeapSort(int a[],int n)
{
int i;
for(i=(n-1)/2;i>=0;i--)
{
HeapAdjust(a,i,n);
}
for(i=n-1;i>=0;i--)
{
swap(a,0,i);
HeapAdjust(a,0,i);
}
cout<<"Heapsort:";
Print(a,n);
}
8、计数排序
计数排序的核心就是将序列中的元素数值转为键值存储在额外申请的数组空间中，其算法复杂度为线性。它使用前提是待排序的元素必须为整数。
算法步骤：
①申请一个额外数组c[Max]，Max为待排序数据元素中的最大值;
②遍历待排序数组，统计每个元素i出现的次数并存储在数组c[i]中;
③计数累加，即c[i]=c[i-1];
④将i元素放在数组的第c[i]项，每放一次就将c[i]减去1；
算法复杂度：O(n)
void CountSort(int a[],int n)
{
int Max;
int i;
int j;
int *b;
Max=MaxValue(a,n);
b=new int[Max+1];
for(i=0;i<=Max;i++)
{
b[i]=0;
}
for(i=0;i<n;i++)
{
b[a[i]]++;
}
j=n-1;
for(i=Max;i>=0;i--)
{
while(b[i])
{
a[j]=i;
b[i]--;
j--;
}
}
cout<<"Countsort:";
Print(a,n);
}
9、基数排序
就是根据元素的的每一位进行排序。基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。（从最低位开始，LSD。从最高位开始MSD)
算法步骤：
①根据待排序序列元素的最低位进行计数排序
②然后根据下一位进行计数排序
③重复步骤②直到最后一位
算法复杂度：O(n)
int GetMaxbit(int a[],int n){ int d=1; int p=10; int i; for(i=0;i<n;i++) { if(a[i]>p) { p=p*10; d++; } } return d;}
void BaseSort(int a[],int n)
{
int i,j;
int d;
int k;
int radix=1;
d=GetMaxbit(a,n);
for(i=0;i<d;i++)
{
int *temp=new int[n];
memset(temp,0,n*sizeof(int));
int *c=new int[10];
memset(c,0,10*sizeof(int));
for(j=0;j<n;j++)
{
k=(a[j]/((int)pow(10.0,i)))%10;
c[k]++;
}
for(j=1;j<10;j++)
{
c[j]=c[j]+c[j-1];
}
for(j=n-1;j>=0;j--)
{
k=(a[j]/((int)pow(10.0,i)))%10;
temp[c[k]-1]=a[j];
c[k]--;
}
for(j=0;j<n;j++)
a[j]=temp[j];
}
cout<<"Basesort:";
Print(a,n);
}
测试代码
//@Description：The summary of sorting algorithm
//@atuther: XiaoYanhan
//@time: 2016-10-20
#include "stdafx.h"
#include "stdlib.h"
#include <stack>
#include <math.h>
#include <iostream>
using namespace std;
void Print(int a[],int n)
{
int i;
for(i=0;i<n;i++)
cout<<a[i]<<' ';
cout<<endl;
}
void BubbleSort(int a[],int n)
{
int i;
int j;
for(i=0;i<n-1;i++)
for(j=0;j<n-i-1;j++)
{
if(a[j]>a[j+1])
{
a[j]=a[j]^a[j+1];
a[j+1]=a[j]^a[j+1];
a[j]=a[j]^a[j+1];
}
}
cout<<"Bubble sort:";
Print(a,n);
}
void InsertSort(int a[],int n)
{
int i;
int j;
int target;
for(i=1;i<n;i++)
{
j=i;
target=a[i];
while(j>0&&target<a[j-1])//从后往前移动较好，target<a[j-1]放在while里面能减少循环次数
{
a[j]=a[j-1];
j--;
}
a[j]=target;
}
cout<<"Insertsort:";
Print(a,n);
}
void ShellInsert(int a[],int n,int delta)
{
int i,j;
int target;
for(i=delta;i<n;i++)
{
target=a[i];
j=i-delta;
while(j>=0&&target<a[j])
{
a[j+delta]=a[j];
j=j-delta;
}
a[j+delta]=target;
}
}
void ShellSort(int a[],int n)
{
int delta;
delta=n/2;
while(delta>=1)
{
ShellInsert(a,n,delta);
delta=delta/2;
}
cout<<"Shell sort:" ;
Print(a,n);
}
void swap(int a[],int i,int j)
{
int temp;
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
int Partion(int a[],int left,int right)
{
int key=left;
while(left<right)
{
while(right>left&&a[right]>=a[key])
right--;
while(left<right&&a[left]<=a[key])
left++;
swap(a,left,right);
}
swap(a,left,key);
return left;
}
void QuickSort(int a[],int left,int right)
{
if(left>=right)
return;
int position;
position=Partion(a,left,right);
QuickSort(a,left,position-1);
QuickSort(a,position+1,right);
}
void Merge(int a[],int left,int mid,int right)
{
int size=right-left+1;
int* temp=new int[size];
int i,k,p;
i=left;
k=mid+1;
p=0;
while(i<=mid&&k<=right)
{
if(a[i]<a[k])
{
temp[p]=a[i];
i++;
}
else
{
temp[p]=a[k];
k++;
}
p++;
}
while(i<=mid)
{
temp[p]=a[i];
p++;
i++;
}
while(k<=right)
{
temp[p]=a[k];
p++;
k++;
}
for(p=0;p<size;p++)
a[left+p]=temp[p];
}
void MergeSort(int a[],int left,int right)
{
int mid;
if(left>=right)
return;
mid=(right-left)/2+left;
MergeSort(a,left,mid);
MergeSort(a,mid+1,right);
Merge(a,left,mid,right);
}
void SelectSort(int a[],int n)
{
int i;
int j;
int MinIndex;
for(i=0;i<n;i++)
{
MinIndex=i;//每次从开始为止寻找最小值的索引，所以初始索引为开始位置
for(j=i+1;j<n;j++)
{
if(a[j]<a[MinIndex])
{
MinIndex=j;
}
}
swap(a,i,MinIndex);
}
cout<<"Selectsort:";
Print(a,n);
}
void HeapAdjust(int a[],int start,int end)
{
int i;
for(i=start*2+1;i<end;i=i*2+1)
{
if(i+1<end)
{
if(a[i]<a[i+1])
i=i+1;
}
if(a[start]>a[i])
break;
else
{
swap(a,start,i);
start=i;
}
}
}
void HeapSort(int a[],int n)
{
int i;
for(i=(n-1)/2;i>=0;i--)
{
HeapAdjust(a,i,n);
}
for(i=n-1;i>=0;i--)
{
swap(a,0,i);
HeapAdjust(a,0,i);
}
cout<<"Heapsort:";
Print(a,n);
}
int MaxValue(int a[],int n)
{
int Max=0;
for(int i=0;i<n;i++)
{
if(a[i]>Max)
Max=a[i];
}
return Max;
}
void CountSort(int a[],int n)
{
int Max;
int i;
int j;
int *b;
Max=MaxValue(a,n);
b=new int[Max+1];
for(i=0;i<=Max;i++)
{
b[i]=0;
}
for(i=0;i<n;i++)
{
b[a[i]]++;
}
j=n-1;
for(i=Max;i>=0;i--)
{
while(b[i])
{
a[j]=i;
b[i]--;
j--;
}
}
cout<<"Countsort:";
Print(a,n);
}
int GetMaxbit(int a[],int n)
{
int d=1;
int p=10;
int i;
for(i=0;i<n;i++)
{
if(a[i]>p)
{
p=p*10;
d++;
}
}
return d;
}
void BaseSort(int a[],int n)
{
int i,j;
int d;
int k;
int radix=1;
d=GetMaxbit(a,n);
for(i=0;i<d;i++)
{
int *temp=new int[n];
memset(temp,0,n*sizeof(int));
int *c=new int[10];
memset(c,0,10*sizeof(int));
for(j=0;j<n;j++)
{
k=(a[j]/((int)pow(10.0,i)))%10;
c[k]++;
}
for(j=1;j<10;j++)
{
c[j]=c[j]+c[j-1];
}
for(j=n-1;j>=0;j--)
{
k=(a[j]/((int)pow(10.0,i)))%10;
temp[c[k]-1]=a[j];
c[k]--;
}
for(j=0;j<n;j++)
a[j]=temp[j];
}
cout<<"Basesort:";
Print(a,n);
}
int _tmain(int argc, _TCHAR* argv[])
{
int arr[10]={8,4,9,0,2,3,6,1,7,5};
int flag;
cout<<"1 BubbleSort"<<endl;
cout<<"2 InsertSort"<<endl;
cout<<"3 ShellSort"<<endl;
cout<<"4 QuickAort"<<endl;
cout<<"5 MergeSort"<<endl;
cout<<"6 SelectSort"<<endl;
cout<<"7 HeapSort"<<endl;
cout<<"8 CountSort"<<endl;
cout<<"9 BaseCout"<<endl;
cin>>flag;
switch(flag)
{
case 1: BubbleSort(arr,10);
break;
case 2: InsertSort(arr,10);
break;
case 3: ShellSort(arr,10);
break;
case 4:
QuickSort(arr,0,9);
cout<<"Quick sort:" ;
Print(arr,10);
break;
case 5:
MergeSort(arr,0,9);
cout<<"Merge sort:" ;
Print(arr,10);
break;
case 6:
SelectSort(arr,10);
break;
case 7:
HeapSort(arr,10);
break;
case 8:
CountSort(arr,10);
break;
case 9:
BaseSort(arr,10);
break;
}
system("PAUSE");
return 0;
}
Paste_Image.png
