常见排序算法一般按平均时间复杂度分为两类：
O(n^2)：冒泡排序、选择排序、插入排序
O(nlogn)：归并排序、快速排序、堆排序
简单排序时间复杂度一般为O(n^2)，如冒泡排序、选择排序、插入排序等
高级排序时间复杂度一般为O(nlogn)，如归并排序、快速排序、堆排序。
两类算法随着排序集合越大，效率差异越大，在数量规模1W以内的排序，两类算法都可以控制在毫秒级别内完成，但当数量规模达到10W以上后，简单排序往往需要以几秒、分甚至小时才能完成排序；而高级排序仍可以在很短时间内完成排序。
一）选择排序：遍历数组元素，找到最小值然后与第n个索引（n=0，1，2...lengh)交换。(不稳定排序)
#include <stdio.h>
void selectsort(int *a,int len)
{
int tmp =0;
int index = 0;
for(int i =0; i<len; i++)
{
tmp = a[i];
index = i;
for(int j = i+1;j<len;j++)
{
if(tmp > a[j])
{
tmp = a[j];
index= j;
}
}
a[index]=a[i];
a[i]=tmp;
}
}
cc
int main()
{
int a[]={342,367,1,989,3,9,235,8,0,432,2};
int number = sizeof(a)/sizeof(int);
selectsort(a,number);
for(int i =0;i<number;i++)
{
printf(" %d",a[i]);
}
return 0;
}
二)冒泡排序：数组内相邻元素比较大小相互交换，循环遍历最大的向下降。（稳定性排序）
#include <stdio.h>
void bubblesqort(int *a,int len)
{
int tmp=0;
for(int i =0;i<len-1;i++)
{
for(int j =0;j<len-1-i;j++)
{
if(a[j]>a[j+1])
{
tmp=a[j];
a[j]=a[j+1];
a[j+1]=tmp;
}
}
}
}
int main()
{
int a[]={342,367,1,989,3,9,235,8,0,432,2};
int number = sizeof(a)/sizeof(int);
bubblesqort(a,number);
for(int i =0;i<number;i++)
{
printf(" %d",a[i]);
}
return 0;
}
三）快速排序：
设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。
一趟快速排序的算法是：
1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；
2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；
3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]和A[i]互换；
4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]互换；
5）重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。
#include <stdio.h>
void qsort(int *a,int nleft, int nright)
{
if(nleft>=nright)
return;
int i =nleft;
int j =nright;
int key =a[i];
while(i<j)
{
while(i<j && a[j]>=key)
j--;
a[i]=a[j];
while(i<j && a[i]<=key)
i++;
a[j]=a[i];
}
a[i]=key;
qsort(a,nleft,i-1);
qsort(a,i+1,nright);
}
int main()
{
int a[]={4321,3,54,57,96567,23,78634,67565,23,78,0,4,56,234,321,1,5546,62634};
int len = sizeof(a)/sizeof(int);
qsort(a, 0, len-1);
for(int i =0;i<len;i++)
{
printf(" %d",a[i]);
}
return 0;
}
四）堆排序
堆排序是利用堆的性质进行的一种选择排序。
利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性，使得每次从无序中选择最大记录(最小记录)变得简单。
（1）用大根堆排序的基本思想
① 先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区
② 再将关键字最大的记录R[1]（即堆顶）和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key
③由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。
……
直到无序区只有一个元素为止。
#include <stdio.h>
//array是待调整的堆数组，i是待调整的数组元素的位置，nlength是数组的长度
//本函数功能是：根据数组array构建大根堆
void HeapAdjust(int array[],int i,int nLength)
{
int nChild;
int nTemp;
for(;2*i+1<nLength;i=nChild)
{
//子结点的位置=2*（父结点位置）+1
nChild=2*i+1;
//得到子结点中较大的结点
if(nChild<nLength-1&&array[nChild+1]>array[nChild])++nChild;
//如果较大的子结点大于父结点那么把较大的子结点往上移动，替换它的父结点
if(array[i]<array[nChild])
{
nTemp=array[i];
array[i]=array[nChild];
array[nChild]=nTemp;
}
else break; //否则退出循环
}
}
//堆排序算法
void HeapSort(int array[],int length)
{
int i;
//调整序列的前半部分元素，调整完之后第一个元素是序列的最大的元素
//length/2-1是最后一个非叶节点，此处"/"为整除
for(i=length/2-1;i>=0;--i)
HeapAdjust(array,i,length);
//从最后一个元素开始对序列进行调整，不断的缩小调整的范围直到第一个元素
for(i=length-1;i>0;--i)
{
//把第一个元素和当前的最后一个元素交换，
//保证当前的最后一个位置的元素都是在现在的这个序列之中最大的
array[i]=array[0]^array[i];
array[0]=array[0]^array[i];
array[i]=array[0]^array[i];
//不断缩小调整heap的范围，每一次调整完毕保证第一个元素是当前序列的最大值
HeapAdjust(array,0,i);
}
}
int main()
{
int i;
int num[]={9,8,7,6,5,4,3,2,1,0};
HeapSort(num,sizeof(num)/sizeof(int));
for(i=0;i<sizeof(num)/sizeof(int);i++)
{
printf("%d ",num[i]);
}
printf("\nok\n");
return 0;
}
五）归并排序
归并排序时的时间复杂度为O（nlgn) 其主要思想是分治法(divide and conquer)，分就是要将n个元素的序列划分为两个序列，再将两个序列划分为4个序列，直到每个序列只有一个元素，最后，再将两个有序序列归并成一个有序的序列。
#include <stdlib.h>
#include <stdio.h>
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[j++];
else
tempArr[k++] = sourceArr[i++];
}
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);
}
}
int main(int argc, char * argv[])
{
int a[8] = {50, 10, 20, 30, 70, 40, 80, 60};
int i, b[8];
MergeSort(a, b, 0, 7);
for(i=0; i<8; i++)
printf("%d ", a[i]);
printf("\n");
return 0;
}
六）插入排序
插入排序就是每一步都将一个待排数据按其大小插入到已经排序的数据中的适当位置，直到全部插入完毕。
#include <stdio.h>
void insert_sort(int *array, unsigned int n)
{
int i,j;
int temp;
for(i=1; i<n;i++)
{
temp = *(array+i);
for(j=i;j>0 && *(array+j-1)>temp;j--)
{
*(array+j) = *(array+j-1);
}
*(array+j)=temp;
}
}
int main()
{
int m[]={223,53,232,43,343435,231,13,56,2,7343,3,64426,23,53462,23,2,6544,3,4};
int len = sizeof(m)/sizeof(int);
insert_sort(m, len);
for(int i = 0;i<len;i++)
{
printf("%d ", m[i]);
}
printf("\n ok\n");
return 0;
}
七）折半插入排序
折半插入排序（binary insertion sort）是对插入排序算法的一种改进，由于排序算法过程中，就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列，这样我们不用按顺序依次寻找插入点，可以采用折半查找的方法来加快寻找插入点的速度。
(减少了比较次数，交换次数一样）
#include<iostream>
using namespace std;
void BinaryInsertSort(int *a,int left,int right){
int tmp ;
int i,low,high,middle,k;
for( i =left+1 ; i<=right ; i++){
tmp = a[i];
low = left;
high = i -1;
while( low <= high ){
middle = (low + high )/2;
if(tmp < a[middle])
high = middle -1;
else
low= middle + 1;
}
for( k = i-1 ; k >= low ; k--)
a[k+1] = a[k];
a[low] = tmp;
}
}
int main(){
int a[]={43,24,54,2,345,3,12,6};
BinaryInsertSort(a,0,7);
for(int i=0;i<8 ;i++)
cout<<a[i]<<" ";
cout<<endl;
return 0;
}
八）希尔排序
希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
希尔(Shell)排序又称为缩小增量排序，它是一种插入排序。它是直接插入排序算法的一种威力加强版。
希尔排序的基本思想是：
把记录按步长gap 分组，对每组记录采用直接插入排序方法进行排序。
随着步长逐渐减小，所分成的组包含的记录越来越多，当步长的值减小到 1 时，整个数据合成为一组，构成一组有序记录，则完成排序
#include <stdio.h>
#include<iostream>
using namespace std;
void ShellSort(int* data,unsigned int len)
{
if(len<=1||data==NULL)
return;
int j = 0;
for(int div=len/2;div>=1;div/=2)
{
for(int i=div;i<len;i++)
{
for( j=i;(j-div>=0)&&(j>=0)&&(data[j]<data[j-div]);j-=div)
{
swap( *(data+j),*(data+j-div));
}
}
}
}
int main()
{
int a[]={345,24,54,2,43,3,12,6};
ShellSort(a,8);
for(int i=0;i<8 ;i++)
cout<<a[i]<<" ";
cout<<endl;
return 0;
}
九）基数排序
实现原理
将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。
#include <stdio.h>
#include<iostream>
using namespace std;
int maxbit(int data[], int n) //辅助函数，求数据的最大位数
{
int d = 1; //保存最大的位数
int p = 10;
for(int i = 0; i < n; ++i)
{
while(data[i] >= p)
{
p *= 10;
++d;
}
}
return d;
}
void radixsort(int data[], int n) //基数排序
{
int d = maxbit(data, n);
int *tmp = new int[n];
int *count = new int[10]; //计数器
int i, j, k;
int radix = 1;
for(i = 1; i <= d; i++) //进行d次排序
{
for(j = 0; j < 10; j++)
count[j] = 0; //每次分配前清空计数器
for(j = 0; j < n; j++)
{
k = (data[j] / radix) % 10; //统计每个桶中的记录数
count[k]++;
}
for(j = 1; j < 10; j++)
count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶
for(j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中
{
k = (data[j] / radix) % 10;
tmp[count[k] - 1] = data[j];
count[k]--;
}
for(j = 0; j < n; j++) //将临时数组的内容复制到data中
data[j] = tmp[j];
radix = radix * 10;
}
delete[]tmp;
delete[]count;
}
int main()
{
int a[]={345,24,54,2,43,3,12,6};
radixsort(a,8);
for(int i=0;i<8 ;i++)
cout<<a[i]<<" ";
cout<<endl;
return 0;
}
网友评论