排序问题
<!--more-->
排序方法 平均情况 最好情况 最坏情况 辅助空间 稳定性
冒泡排序 O(n^2) O(n) O(n^2) O(1) 稳定
选择排序 O(n^2) O(n^2) O(n^2) O(1) 不稳定
插入排序 O(n^2) O(n) O(n^2) O(1) 稳定
希尔排序O(n*log(n))~O(n^2) O(n^1.3) O(n^2) O(1) 不稳定
堆排序 O(nlog(n)) O(nlog(n)) O(n*log(n)) O(1) 不稳定
归并排序 O(nlog(n)) O(nlog(n)) O(n*log(n)) O(n) 稳定
快速排序 O(nlog(n)) O(nlog(n)) O(n^2) O(1) 不稳定
关于稳定性： 假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的;否则称为不稳定的。
（一）冒泡排序
基本思想 ：在一组没有排序的数组中，通过自上而下对相邻的两个数进行比较，让较大的数下沉
即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换
时间复杂度 ：无论给定什么数列，都需要比较 n（n-1）,则为 O(n^2)
// 冒泡排序，返回升序数组
publicstaticvoidbubbleSort(inta[],intn) {
for(inti=0;i<n-1;i++) {
for(intj=0;j<n-1-i;j++)
if(a[j]>a[j+1]) {
inttmp=a[j];
a[j]=a[j+1];
a[j+1]=tmp;
}
}
}
改进的冒泡排序 ：
改进后，当传入的数组为已经排序的的时，只需进行 n 次比较，则为 O(n)，为最优情况
对冒泡排序常见的改进方法是加入一标志性变量flag，用于标志某一趟排序过程中是否有数据交换，如果进行某一趟排序时并没有进行数据交换，则说明数据已经按要求排列好，可立即结束排序，避免不必要的比较过程
// 冒泡排序，返回升序数组
publicstaticvoidbubbleSort_1(inta[],intn) {
booleanflag;
for(inti=0;i<n-1;i++) {
flag=false;
for(intj=0;j<n-1-i;j++)
if(a[j]>a[j+1]) {
inttmp=a[j];
a[j]=a[j+1];
a[j+1]=tmp;
flag=true;
}
if(flag==false)
break;
}
}
对于每次的排序，记录下交换的位置pos,则当一次排序结束后，可以得到最后一次排序的坐标，当下一趟排序开始时，只需要比较到pos 就可以了，因为pos 后面的都已经排序好了。
publicstaticvoidbubbleSort_2(intr[],intn) {
inti=n-1;// 初始时,最后位置保持不变
while(i>0) {
intpos=0;// 每趟开始时,无记录交换
for(intj=0;j<i;j++)
if(r[j]>r[j+1]) {
pos=j;// 记录交换的位置
inttmp=r[j];
r[j]=r[j+1];
r[j+1]=tmp;
}
i=pos;// 为下一趟排序作准备
}
}
（二）选择排序
算法思想 ：在第一次排序，扫描N个数据，选出其中的最小值，与第一个元素交换，接着进行第二趟，以此类推
复杂度 ： 平均时间复杂度：O(n2)。当有重复元素时，会改变位置，比如【2,2,5】，第一趟第1,2就会交换位置，所以此算法为不稳定的。
// 选择排序
staticvoidselectionSort(inta[],intn) {
intindex;
for(inti=0;i<n;i++) {
index=i;
for(intj=i+1;j<n-1;j++) {
if(a[j]<a[index])
index=j;
if(index!=i) {
inttmp=a[index];
a[index]=a[i];
a[i]=tmp;
}
}
}
}
(三) 插入排序
算法思想 ：把数据分成有序组和插入组，一般把第一个元素当成有序组，然后从插入组中拿第一个数据，从有序组的最后一个元素进行比较，找到合适的位置并插入，为稳定排序。
时间复杂度 ：当给定的数据为排序升序时，只要比较N 次，为O(n)；当是降序时，要 n(n+1)/2，所以为O(n^2)
平均的时间复杂度为O(n^2)。
//插入排序
publicstaticvoidInsertionSort(inta[],intn)
{
inti=0;
intj=0;
inttmp=0;
for(i=1;i<n;i++)
{
tmp=a[i];//从待插入组取出第一个元素。
j=i-1;//i-1即为有序组最后一个元素（与待插入元素相邻）的下标
while(j>=0&&tmp<a[j])//注意判断条件为两个，j>=0对其进行边界限制。第二个为插入判断条件
{
a[j+1]=a[j];//若不是合适位置，有序组元素向后移动
j--;
}
a[j+1]=tmp;//找到合适位置，将元素插入。
}
}
（四）希尔排序
算法思想 : 将无序数组分割为若干个子 序列，子序列不是逐段分割的，而是相隔特定的增量的子序列，对各个子序列进行插入排序；然后再选择一个更小的增量，再将数组分割为多个子序列进行排序......最后选择增量为1，即使用直接插入排序，使最终数组成为有序。
时间复杂度 ：O(n*log(n))~O(n^2) ，最坏情况为O(n^2)
// 希尔排序
publicstaticvoidshell_sort(intarr[],intsize) {
if(arr==null)
return;
inth=1;/* 关于步长，取值没有统一标准，必须小于size，最后一次步长要为1 */
/* 计算首次步长 */
while(h<size/3)
h=3*h+1;
inti,j,temp;
while(h>=1) {
for(i=h;i<size;++i) {
/* 将a[i]插入到a[i-h]、a[i-2h]、a[i-3h]...中 */
for(j=i;j>=h&&(arr[j]<arr[j-h]);j-=h) {
temp=arr[j];
arr[j]=arr[j-h];
arr[j-h]=temp;
}
}
/* 计算下一轮步长 */
h=h/3;
}
}
（五）快速排序
快速排序 ：选取一个数，位置i，进行排序比较，从j开始，选择比选取的数小的，填补到原来的位置，则此时j位置，空出来，再从i++开始，选择比i大的数，填补到j的位置，重复排序,则是大的放右边，小的左边，然后继续递归调动。
时间复杂度 ：O(N*logN)
//快速排序
voidquick_sort(ints[],intl,intr)
{
if(l<r)
{
inti=l,j=r,x=s[l];
while(i<j)
{
while(i<j&&s[j]>=x)// 从右向左找第一个小于x的数
j--;
if(i<j)
s[i++]=s[j];
while(i<j&&s[i]<x)// 从左向右找第一个大于等于x的数
i++;
if(i<j)
s[j--]=s[i];
}
s[i]=x;
quick_sort(s,l,i-1);// 递归调用
quick_sort(s,i+1,r);
}
}
网友评论