1.排序算法简要比较
| 名称 | 数据对象 | 稳定性 | 时间复杂度 | 空间复杂度 | 描述 | ||
|---|---|---|---|---|---|---|---|
| 平均 | 最坏 | ||||||
| 插入排序 | 数组、链表 | √ |  |
O(1) | (有序区,无序区)。把无序区的第一个元素插入到有序区的合适的位置。对数组：比较得少，换得多。 | ||
| 直接选择排序 | 数组 | × | |
O(1) | (有序区,无序区)。在无序区里找一个最小的元素跟在有序区的后面。 对数组：比较得多，换得少。 | ||
| 链表 | √ | ||||||
| 堆排序 | 数组 | × | O(nlogn) | O(1) | (最大堆,有序区)。从堆顶把根卸出来放在有序区之前，再恢复堆。 | ||
| 归并排序 | 数组、链表 | √ | O(nlogn) | O(n) +O(logn) ， 如果不是从下到上 | 把数据分为两段，从两段中逐个选最小的元素移入新数据段的末尾。可从上到下或从下到上进行。 | ||
| 快速排序 | 数组 | × | O(nlogn) | |
O(logn) ,O(n) | (小数,枢纽元,大数)。 | |
| Accum qsort | 链表 | √ | O(nlogn) | |
O(logn) ,O(n) | (无序区,有序区)。把无序区分为(小数,枢纽元,大数)，从后到前压入有序区。 | |
| 决策树排序 | √ | O(logn!) | O(n!) | O(n) <O(logn!) <O(nlogn) | |||
| 计数排序 | 数组、链表 | √ | O(n) | O(n+m) | 统计小于等于该元素值的元素的个数 i，于是该元素就放在目标数组的索引 i位。(i≥0) | ||
| 桶排序 | 数组、链表 | √ | O(n) | O(m) | 将值为 i 的元素放入i 号桶，最后依次把桶里的元素倒出来。 | ||
| 基数排序 | 数组、链表 | √ | 一种多关键字的排序算法，可用桶排序实现。 | ||||
- 均按从小到大排列
- n 代表数据规模
- m 代表数据的最大值减最小值
2.冒泡排序：
冒泡排序基本思路：
冒泡排序的主要思想就是通过一趟排序，将数组中的最大值转移到的数组最后一个元素。一个有n个元素的数组，那么经过(n-1)趟排序以后，就能够完成排序。因为如果(n-1)个元素的位置确定了，那么最后的那一个元素的位置也就确定了。还有需要注意的是每一趟排序都能确定数组中的一个元素位置，因此经过一趟排序以后，需要进行排序比较的元素就减少一个。
在每一趟排序过程中，都是从数组元素第一个开始，依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。由于在排序过程中总是小数往前放，大数往后放，相当于气泡往上升，所以称作冒泡排序。
冒泡排序的改进
冒泡排序法存在的不足及改进方法：
第一，在排序过程中，执行完当前的第k趟排序后，可能数据已全部排序完备，但是程序无法判断是否完成排序，会继续执行剩下的(n-1-k)趟排序。为了解决这一不足，可以设置一个标志位flag，将其初始值设置为非0，表示被排序的数组是一个无序的数组。每一次排序开始前设置flag值为0，表示假设已经完成排序，如果这一趟排序过程中都没有数据发生交换，则flag的值就为0；但是当这一趟排序过程中存在数据交换时，修改flag为非0，表示这一趟仍然有数据没有完成排序。在新一轮排序开始时，检查此标志，若此标志为0，表示上一次没有做过交换数据，则表示经过上一趟的排序，已经完成了对数组的排序，排序结束；否则继续进行排序；
根据上述思路进行改进的冒泡排序代码实现如下：
View Code
void bubbleSortImproved(int arry[],int len) { int flag=1;//表明数组是无序的 for(int i=0;i<len-1;i++)//排序len-1趟 { if(flag)//数组无序则需要继续进行排序 { flag=0;//出事设置flag=0表明已排序完成 for(int j=0;j<len-1-i;j++)//每次比较前从arry[0]到arry[len-1-i]的元素，随着趟数增加，需要比较的元素越来越少 { if(arry[j]>arry[j+1])//如果一个数比相邻的后面一个数大，则交换位置 { swap(arry,j,j+1); flag=1;//如果还有元素交换，则flag=0 } } } else//如果数组已经有序，则跳出循环，无需进行排序 break; } }
第二，当排序的数据比较多时排序的时间会明显延长。改进方法：快速排序：具体做法：任意选取某一记录（通常取第一个记录），比较其关键字与所有记录的关键字，并将关键字比它小的记录全部放在它的前面，将比它大的记录均存放在它的后面，这样，经过一次排序之后，可将所有记录以该记录所在的分界点分为两部分，然后分别对这两部分进行快速排序，直至排序完。也就是说，利用快速排序过程中的Partition()方法返回的index将需要排序的元素分为两段，在index前面的数据都比index位置的数据小，在index后面的元素都比index位置的数据大。然后对前后两段数据进行冒泡排序，这样缩小的冒泡排序的数据量。
局部冒泡排序算法对冒泡排序的改进：
在冒泡排序中，一趟扫描有可能无数据交换，也有可能有一次或多次数据交换，在传统的冒泡排序算法及近年来的一些改进的算法中，只记录一趟扫描有无数据交换的信息，对数据交换发生的位置信息则不予处理。为了充分利用这一信息，可以在一趟全局扫描中，对每一反序数据对进行局部冒泡排序处理，称之为局部冒泡排序。局部冒泡排序与冒泡排序算法具有相同的时间复杂度，并且在正序和逆序的情况下，所需的关键字的比较次数和移动次数完全相同。由于局部冒泡排序和冒泡排序的数据移动次数总是相同的，而局部冒泡排序所需关键字的比较次数常少于冒泡排序，这意味着局部冒泡排序很可能在平均比较次数上对冒泡排序有所改进，当比较次数较少的优点不足以抵消其程序复杂度所带来的额外开销，而当数据量较大时，局部冒泡排序的时间性能则明显优于冒泡排序。
3.快速排序
参考前面写的博文：
冒泡排序与快速排序代码实现
View Code
#include<iostream> #include<stdlib.h> using namespace std; void swap(int arry[],int a,int b) { int temp=arry[a]; arry[a]=arry[b]; arry[b]=temp; } //冒泡排序 void bubble_sort(int arry[],int len) { for(int i=0;i<len-1;i++)//需要遍历(len-1)趟 for(int j=0;j<len-1-i;j++)//每遍历一趟减少确定一个数字，所以减少一个比较数字 { if(arry[j]>arry[j+1]) swap(arry,j,j+1); } } //快速排序2，不交换，直接赋值。 int partition2(int arry[],int start,int end) { int pivot=arry[start]; while(start<end) { while(start<end&&arry[end]>pivot) end--; arry[start]=arry[end];//逆向找出第一个小于pivot的值，将其移到start这一边 while(start<end&&arry[start]<pivot) start++; arry[end]=arry[start];//正向找出第一个大于pivot的值，将其移到end这一边 } arry[start]=pivot; return start; } //快速排序1,交换数组中的元素。 int partition(int arry[],int start,int end) { int pivot=arry[start]; while(start<end) { while(start<end&&arry[end]>pivot) end--; swap(arry,start,end); while(start<end&&arry[start]<pivot) start++; swap(arry,start,end); } arry[start]=pivot; return start; } //快速排序 void qsort(int arry[],int start,int end,int len) { int pivotkey=partition(arry,start,end); if(start<end) { qsort(arry,start,pivotkey-1,len); qsort(arry,pivotkey+1,end,len); } } void print(int arry[],int len) { for(int i=0;i<len;i++) cout<<arry[i]<<" "; cout<<endl; } void test_bubble() { int arry[]={3,8,7,1,9}; int len=sizeof(arry)/sizeof(int); print(arry,len); bubble_sort(arry,len); print(arry,len); } void test_qsort() { int arry[]={3,8,7,1,9}; int len=sizeof(arry)/sizeof(int); print(arry,len); qsort(arry,0,len-1,len); print(arry,len); } void main() { test_bubble(); test_qsort(); system("pause"); }
4.堆排序
堆排序的主要思路：
- 一般情况下都使用数组实现堆的结构，以大顶堆为例，因为是使用数组，元素下表从0开始，所以要求arry[i]>arry[i*2+1]，arry[i]>arry[i*2+2]。表示父结点大于其左右孩子结点的值。
- 所以堆排序的第一步是根据其实数组元素，构建一个堆。构建堆就需要调整堆中的元素，从第一个非叶子结点开始调整，第一个非叶子结点的位置是t=(len/2-1)。因为堆是一棵满二叉树的结构，所以从0到t的所有结点都是非叶子结点。
- 在调整堆结构过程中，我们需要比较父节点与其左右子结点的值，可以先求出左右子结点的最大值，即c=max(arry[leftChild],arry[rightChild])，然后将这个最大值与父节点arry[parent]进行比较，如果父节点小于子节点，那么交换父节点与子节点的值（子节点中较大的那个元素），如果父节点大与子节点，则表明满足堆结构要求，不需要交换。在调整的过程中可能会出现一种情况，比如父节点A与子节点B进行交换，此时A结点是B结点的子节点，但是A结点又是CD两个结点的父节点，因此我们还需要调整ACD三个元素位置，一直调整到结点没有子节点为止。
- 在堆排序中，首先是构建一个最大堆，此处需要用到buildHeap(int arry[],int len)这个函数，而这个函数中又调用了adjustHeap(int arry[],int parent,int len)，所以可以将build看成是由adjustheap组成的。在构建完成以后，我们交换首元素与末元素的位置，交换以后我们知道首元素不符合最大堆的定义，所以需要调整首元素的位置，也就是adjustHeap(arry,0,len-i-1)。
- 我们可以发现adjustHeap(int arry[],int parent,int len)的时间复杂读是o(logn)，而需要调用o(n)次这个方法啊，所以时间复杂度时o(nlogn)
堆排序的代码实现
c++实现
View Code
#include<iostream> #include<stdlib.h> #include<stack> using namespace std; //函数声明 void PrintArry(int arry[],int len);//打印数组 void swap(int arry[],int i,int j);//交换数组元素 void AdjustHeap(int arry[],int parent,int len);//调整堆，使其满足堆的要求 void BuildHeap(int arry[],int len);//初始化堆 void HeapSort(int arry[],int len);//堆排序 void PrintArry(int arry[],int len) { for(int i=0;i<len;i++) cout<<arry[i]<<" "; cout<<endl; } void swap(int arry[],int i,int j) { int temp=arry[i]; arry[i]=arry[j]; arry[j]=temp; } void AdjustHeap(int arry[],int parent,int len) { int c=parent*2+1;//parent的左孩子结点，这里+1是因此头结点从0开始 while(c<len)//如果左孩子小于堆长度 { if(c+1<len&&arry[c]<arry[c+1])//如果右孩子小于对长度并且右孩子大于左孩子，则获取右孩子的坐标 c++; if(arry[parent]>=arry[c])//如果父节点比孩子结点大则退出循环 { break; } else { swap(arry,parent,c);//如果孩子结点比父节点大，则交换 //因为孩子结点也可能是父结点，所以接下来继续调整孩子结点，直到父节点大于两个孩子结点或者没有孩子结点为止。 parent=c; c=parent*2+1; } } } //初始化堆 void BuildHeap(int arry[],int len) { int begin=len/2-1;//从第一个非叶子结点开始调整，直到最后的根结点，根结点是arry[0] for(int i=begin;i>=0;i--) { AdjustHeap(arry,i,len); } } void HeapSort(int arry[],int len) { //创建初始化堆，用数组实现堆的结构。 BuildHeap(arry,len); //在初始化堆以后数组首元素arry[0]是最大的，交换首元素与堆的末尾元素， //这样就完成了对一个数排序，堆的长度-1 for(int i=0;i<len;i++) { swap(arry,0,len-1-i);//交换堆顶元素与堆末尾元素 AdjustHeap(arry,0,len-1-i);//交换以后继续调整整个堆的结构 } } void main() { int arry[]={1,3,6,2,7,0,8,5}; int len=sizeof(arry)/sizeof(int); PrintArry(arry,len); HeapSort(arry,len); PrintArry(arry,len); system("pause"); }
java实现（ps：2012-10-8）
View Code
public class HeapSortDemo { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub int arry[]={1,3,6,2,7,0,8,5}; int len=arry.length; printArry(arry,len);//打印数组 //testswap(arry);//测试swap方法，该方法交换元素不需要创建临时变量。 heapSort(arry,len); printArry(arry,len);//打印数组 } public static void testswap(int arry[]) { System.out.println(arry[1]+" "+arry[2]); swap(arry,1,2); System.out.println(arry[1]+" "+arry[2]); } //不创建临时变量交换两个元素的值 public static void swap(int arry[],int i,int j) { arry[i]=arry[i]^arry[j]; arry[j]=arry[i]^arry[j]; arry[i]=arry[i]^arry[j]; } //堆排序 public static void heapSort(int arry[],int len) { buildHeap(arry,len);//建立最大堆 for(int i=0;i<len;i++) { swap(arry,0,len-1-i);//在构建完最大堆以后，数组首元素就是最大值，将其与最后一个元素交换位置，此时最后一个元素已排好序。 adjustHeap(arry,0,len-i-1);//交换首元素以后需要重新调整首元素的位置。所以这里adjustHeap(arry,0,len-1-i)，其中0就表示首元素 } } //由底自顶构建堆 public static void buildHeap(int arry[],int len) { int nonleaf=len/2-1;//如果一个满二叉树有len个节点，那么从后往前找第一个非叶子节点应该是在第len/2个，但是因为此处第一个为0，所以len/2要-1 for(int i=nonleaf;i>=0;i--) { adjustHeap(arry,i,len);//从第一个父节点，也就是第一个非叶子结点开始调整 } } public static void printArry(int arry[],int len) { for(int i=0;i<len;i++) System.out.print(arry[i]+" "); System.out.println(); } //由顶自底调整堆 public static void adjustHeap(int arry[],int parent,int len) { int left=parent*2+1;//左节点 while(left<len) { if(left+1<len&&arry[left]<arry[left+1])//如果存在右节点，并且左节点小于右节点，那么就应该将右节点与父节点进行比较 left++;//此时left代表右节点 if(arry[parent]>=arry[left])//如果父节点大于叶子节点，则退出循环，表示已经构建好堆 break; else { swap(arry,parent,left); parent=left; left=parent*2+1; } } } }
此处使用异或方法交换两个元素的值存在一些bug，建议还是使用常规的交换元素方法。
5.归并排序
参考文献：白话经典算法系列之五 归并排序的实现
5.1归并排序思路
- 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。分治的思想类似于快速排序，不过它比快速排序多了一步merge。首先考虑下如何将将二个有序数组A/B合并的问题。这个非常简单，设定两个指针分别指向A和B的首地址，然后比较这两个指针所指向的数，哪一个数小就将其保存到临时数组T中，然后指针往前移动一个位置。比如指针pa指向数组A的首地址，pb指向数组B的首地址，指针pt指向临时数组的首地址。加入pa指向的数小于pb指向的数，则将pa所指向的数存放在pt所指的位置上，然后pa和pt都往前移动一格。重复上述操作，直到pa和pb有一个指向数组的末尾元素。此时将另外一个指针没有指向末尾元素的数组中的元素全部都保存到临时数组中。这样就完成了两个有序数组的归并操作。
- 解决了上面的合并有序数列问题，再来看归并排序，其的基本思路就是将一个数组分成二组，分为A和B，如果这二组组内的数据都是有序的，那么就可以很方便的将这二组数据进行归并。那么如何让这二组组内数据有序了？可以将A，B组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序。
5.2代码示例
View Code
void printArry(int arry[],int len) { for(int i=0;i<len;i++) { cout<<arry[i]<<" "; } cout<<endl; } //归并两段相邻的有序数组 void MergeArry(int arry[],int start,int mid,int end,int temp[]) { int i=start;//第一段有序数组的起始位置 int j=mid+1;//第二段有序数组的起始位置 int k=0;//临时数组的坐标 while(i<=mid&&j<=end)//两个起始指针都没有走到数组末尾 { if(arry[i]<arry[j])//如果第一段中的元素比第二段中的元素小 temp[k++]=arry[i++];//将第一段中的元素赋值给临时数组 else temp[k++]=arry[j++]; } //有一段数组没有遍历到末尾，进行赋值 while(i<=mid) temp[k++]=arry[i++]; while(j<=end) temp[k++]=arry[j++]; //将临时数组中的元素重新赋值给原始数组的指定位置 for(i=0;i<k;i++) arry[start+i]=temp[i]; } //归并排序，传入原始数组，排序的起始与末尾位置以及临时数组 void MergeSort(int arry[],int start,int end,int temp[]) { if(start<end) { int mid=(start+end)/2;//数组重点 MergeSort(arry,start,mid,temp);//递归调用，排序前半段arry[start...mid] MergeSort(arry,mid+1,end,temp);//递归调用，排序后半段arry[mid+1,end] MergeArry(arry,start,mid,end,temp);//归并上述两段有序数组。 } } //归并排序，传入参数为数组与数组长度 void MergeSort(int arry[],int len) { //创建临时数组，在这里创建临时数组比在后面创建临时数组的开销要小，后面所有递归调用用的都是同一个临时数组 int *temp=new int[len]; int start=0; int end=len-1; //调用重载方法的归并排序 MergeSort(arry,start,end,temp); } void main() { int arry[]={3,5,3,6,4,7,5,7,4}; int len=sizeof(arry)/sizeof(int); printArry(arry,len); MergeSort(arry,len); printArry(arry,len); system("pause"); }
注意点：
在这里我们看到我们merge的分段是arry[start...mid]跟arry[mid+1...end]，我们不能分成arry[start...mid-1]跟arry[mid...end]，这是因为mid=(start+end)/2，假如start=1，end=2，则mid=1，此时调用MergeSort(arry,start=1,end=3,temp);会就变成了MergeSort(arry,mid=1,end=3,temp)的死循环了。