排序算法
? ? ? ?在笔试、面试过程中，经常会考排序算法，下面我将介绍几种常用的排序算法（以由小到大排序为例）。
各个排序算法的时间复杂度、稳定性，如右图所示 稳定性：如果按照健对记录进行排序，排序后，如果具有相同健的记录的相对位置保持不变，则排序算法是稳定的 |
|---|
直接插入排序
? ? ? ?将数据分成有序区和无序区。每次遍历时，将无序区的数据插入到有序区。
#include "stdafx.h"
#include <stdlib.h>
#include<time.h>
int *GenerateRandArray(int len){
int *array=(int *)malloc(sizeof(int)*len);
srand((int)time(NULL));
for(int i=0;i<len;i++)
{
array[i]=rand();
}
return array;
}
int *InsertSort(int * array,int len){
int p;
int j;
for(int i=0;i+1<len;i++){
j=i+1;
if(array[j]<array[i]){
p=array[j];
while(i>=0&&array[i]>p){
array[i+1]=array[i];
i--;
}
array[i+1]=p;
i=j-1;
}
}
return array;
}
void print(int *array,int len){
if(!array)
return ;
for(int i=0;i<len-1;i++)
printf("%d\t",array[i]);
printf("%d\n",array[i]);
}
int main(int argc, char* argv[])
{
int len=10;
int *array=GenerateRandArray(len);
print(array,len);
InsertSort(array,len);
print(array,len);
return 0;
}冒泡排序
? ? ? ?也是将数据分成无序区和有序区：前面是无序的，末尾是有序的。每次遍历时，比较相连的两个数据，如果前面的数据较大，则和后面的数据交换。这样，遍历一次，会将无序区中最大的数据移动到末尾。
? ? ? ?由于遍历的时候，可能排序已经完成了，这就需要设置一个标记flag，判断数组是否已经排序好了。
int *BubbleSort(int *array,int len)
{
int i,j,p;
bool isChanged;
for(j=len-1;j>0;j--)
{
isChanged=false;
for(i=0;i<j;i++)
{
if(array[i]>array[i+1])
{
isChanged=true;
p=array[i];
array[i]=array[i+1];
array[i+1]=p;
}
}
if(!isChanged)
break;
}
return array;
}快速排序
? ? ? ?随机选择一个数，将数组分为比该数小和比该数大的两个部分，然后分别对两个区域进行排序。函数Partition除了可以用在快速排序算法中，还可以用来实现在长度为n的数组中查找第k大的数字、最大的k个数、最小的k个数
时间复杂度：O(NlogN) |
|---|
? ? ? 参考：快速排序及其优化
#include "stdafx.h"
#include <iostream>
using namespace std;
#define N 5
void swap(int *data,int a,int b){
int tmp=data[b];
data[b]=data[a];
data[a]=tmp;
}
int Partition(int data[],int length,int start,int end){
if(NULL==data||length<=0||start<0||end>=length)
throw new std::exception("Invalid Exception");
int small=start-1;
int index=(start+end)/2;
swap(data,index,end);
for(index=start;index<end;index++)
{
if(data[index]<data[end])
{
small++;
if(small<index)
{
swap(data,small,index);
}
}
}
small++;
swap(data,small,end);
return small;
}
void QuickSort(int data[],int length,int start,int end){
if(start==end)
return;
int index=Partition(data,length,start,end);
if(index>start)
QuickSort(data,length,start,index-1);
else
QuickSort(data,length,index+1,end);
}
int main(int argc, char* argv[])
{
int src[]={1,3,1,21,32141,13241,12,323,12};
int len=sizeof(src)/sizeof(int);
QuickSort(src,len,0,len-1);
for(int i=0;i<len;i++)
cout<<src[i]<<"\t";
return 0;
}选择排序
? ? ? ?将数据分成无序区和有序区：前面是有序的，末尾是无序的。每次遍历时，从无序区选择最小的数据遍历到有序区。
int *SelectSort(int * array,int len)
{
int i,j,k,p;
for(i=0;i<len-1;i++)
{
k=i;
for(j=i+1;j<len;j++)
{
if(array[j]<array[k])
{
k=j;
}
}
p=array[k];
array[k]=array[i];
array[i]=p;
}
return array;
}堆排序
? ? ? ?大根堆：array[i]>=array[2*i+1]，array[i]>array[2*i+2]；如果构造成二叉树的时候，其跟节点大于左右节点；?数据也分为无序区和有序区，有序区在末尾，每次遍历时，将根节点移动到无序区的末尾，这样反复就排好序了。
时间复杂度：O(NlogN) 缺陷：在实践中由于不如快速排序，所以很少用 意义：最快的找到最大/最小值，在堆结构中，插入一个值，取走最大/最小值后重新构建堆结构，时间复杂度为O(logN)，其他方法最小为O(N) 堆在实践中的用途不在于排序，主要用在调度算法中，比如优先级调度，每次取优先级最高的，时间驱动，取时间最小/等待最长的等等，分为最大堆/最小堆 |
|---|
void swap(int *array,int i,int j)
{
int p=array[i];
array[i]=array[j];
array[j]=p;
}
void HeapAdjust(int *array,int i,int n){
if(1==n||i>(n-2)/2) return;
int left=2*i+1,right=2*i+2;
int p=array[i];
if(right>n-1){
if(p>array[left])
return;
swap(array,i,left);
HeapAdjust(array,left,n);
}else
{
if(p>=array[left]&&p>=array[right]) return;
int max=right;
if(p<array[left]&&array[right]<=array[left])
{
max=left;
}
swap(array,i,max);
HeapAdjust(array,max,n);
}
}
void HeapBuild(int *array,int n)
{
for(int i=(n-1)/2;i>=0;i--)
HeapAdjust(array,i,n);
}
int * HeapSort(int *array,int len)
{
HeapBuild(array,len);
for(int i=len-1;i>0;i--){
swap(array,0,i);
HeapAdjust(array,0,i);
}
return array;
}归并排序
? ? ? ?将数据均分成两个部分，分别排序，然后合并。
? ? ? ?时间复杂度：O(nlogn)
void Merge(int *array,int left,int middle,int right)
{
int i,j,k,N=right-left+1;
int *pArray=(int *)malloc(N*sizeof(int));
for(i=left,j=middle+1,k=0;i<=middle&&j<=right;k++){
if(array[i]<array[j]){
pArray[k]=array[i];
i++;
}
else
{
pArray[k]=array[j];
j++;
}
}
if(i<=middle){
while(k<N)
pArray[k++]=array[i++];
}
for(i=0;i<k;i++)
array[i+left]=pArray[i];
free(pArray);
}
int *MergeSort(int *array,int left,int right){
if(right-left<=0) return array;
int i=(left+right)/2;
MergeSort(array,left,i);
MergeSort(array,i+1,right);
Merge(array,left,i,right);
return array;
}
int *MergeSort(int *array,int len)
{
return MergeSort(array,0,len-1);
}基数排序
? ? ? ?基数排序又称桶排序，他是基于健的，将数据分在若干个桶中，以达到排序的目的。
? ? ??将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。 ? ? 基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。
? ? ? ?时间复杂度：O (d(n+r))，其中r为所采取的堆数，d为数据的长度
int getDigit(int *array,int index,int pos){
int N=1;
while(--pos>0)
N*=10;
return array[index]/N%10;
}
int *LsdRadixSort(int *array,int begin,int end,int d) {
int i,j,N=end-begin+1;
int *bucket=(int *)malloc(N*sizeof(int));
for(int pos=1;pos<=d;pos++){
int count[10]={0};
for(i=begin;i<=end;i++)
count[getDigit(array,i,pos)]++;
for(i=0;i<9;i++)
count[i+1]+=count[i];
for(i=end;i>=begin;i--)
bucket[--count[getDigit(array,i,pos)]]=array[i];
for(i=begin,j=0;i<=end;)
array[i++]=bucket[j++];
}
free(bucket);
return array;
}
int *LsdRadixSort(int *array,int len)
{
int max=array[0];
for(int i=1;i<len;i++)
if(array[i]>max)
max=array[i];
int d=1;
while(max/=10)
d++;
return LsdRadixSort(array,0,len-1,d);
}参考文献： 八大排序算法总结