概述
排序有內(nèi)部排序和外部排序，內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進(jìn)行排序，而外部排序是因排序的數(shù)據(jù)很大，一次不能容納全部的排序記錄恋腕，在排序過程中需要訪問外存。我們這里說說八大排序就是內(nèi)部排序逆瑞。
當(dāng)n較大荠藤，則應(yīng)采用時(shí)間復(fù)雜度為O(nlog2n)的排序方法：快速排序、堆排序或歸并排序序获高。
快速排序：是目前基于比較的內(nèi)部排序中被認(rèn)為是最好的方法哈肖，當(dāng)待排序的關(guān)鍵字是隨機(jī)分布時(shí)，快速排序的平均時(shí)間最短念秧；
1.插入排序—直接插入排序(Straight Insertion Sort)
基本思想:
將一個(gè)記錄插入到已排序好的有序表中淤井，從而得到一個(gè)新，記錄數(shù)增1的有序表摊趾。即：先將序列的第1個(gè)記錄看成是一個(gè)有序的子序列币狠，然后從第2個(gè)記錄逐個(gè)進(jìn)行插入，直至整個(gè)序列有序?yàn)橹埂?br>
要點(diǎn)：設(shè)立哨兵砾层，作為臨時(shí)存儲和判斷數(shù)組邊界之用总寻。
直接插入排序示例：
如果碰見一個(gè)和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面梢为。所以，相等元素的前后順序沒有改變，從原無序序列出去的順序就是排好序后的順序铸董，所以插入排序是穩(wěn)定的祟印。
算法的實(shí)現(xiàn)：
package com;
public class InsertSort {
public static void main(String[] args) {
int a[] = {3,1,5,7,2,4,9,6,10,8};
InsertSort obj=new InsertSort();
System.out.println("初始值：");
obj.print(a);
obj.insertSort(a);
System.out.println("\n排序后：");
obj.print(a);
}
public void print(int a[]){
for(int i=0;i<a.length;i++){
System.out.print(a[i]+" ");
}
}
public void insertSort(int[] a) {
for(int i=1;i<a.length;i++){//從頭部第一個(gè)當(dāng)做已經(jīng)排好序的，把后面的一個(gè)一個(gè)的插到已經(jīng)排好的列表中去粟害。
if(a[i]<a[i-1]){
int j;
int x=a[i];//x為待插入元素
a[i]=a[i-1];
for(j=i-1; j>=0 && x<a[j];j--){//通過循環(huán)蕴忆，逐個(gè)后移一位找到要插入的位置。
a[j+1]=a[j];
}
a[j+1]=x;//插入
}
}
}
}
效率：
時(shí)間復(fù)雜度：O（n^2）.
其他的插入排序有二分插入排序悲幅，2-路插入排序套鹅。
- 插入排序—希爾排序（Shell`s Sort）
希爾排序是1959 年由D.L.Shell 提出來的，相對直接排序有較大的改進(jìn)汰具。希爾排序又叫縮小增量排序
基本思想：
先將整個(gè)待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序卓鹿，待整個(gè)序列中的記錄“基本有序”時(shí)，再對全體記錄進(jìn)行依次直接插入排序留荔。
操作方法：
選擇一個(gè)增量序列t1吟孙，t2，…聚蝶，tk杰妓，其中ti>tj，tk=1碘勉；
按增量序列個(gè)數(shù)k巷挥，對序列進(jìn)行k 趟排序；
每趟排序验靡，根據(jù)對應(yīng)的增量ti倍宾，將待排序列分割成若干長度為m 的子序列，分別對各子表進(jìn)行直接插入排序晴叨。僅增量因子為1 時(shí)栅受，整個(gè)序列作為一個(gè)表來處理，表長度即為整個(gè)序列的長度耻矮。
希爾排序的示例：
算法實(shí)現(xiàn)：
我們簡單處理增量序列：增量序列d = {n/2 ,n/4, n/8 .....1} n為要排序數(shù)的個(gè)數(shù)
即：先將要排序的一組記錄按某個(gè)增量d（n/2,n為要排序數(shù)的個(gè)數(shù)）分成若干組子序列贸毕，每組中記錄的下標(biāo)相差d.對每組中全部元素進(jìn)行直接插入排序，然后再用一個(gè)較小的增量（d/2）對它進(jìn)行分組孙技，在每組中再進(jìn)行直接插入排序产禾。繼續(xù)不斷縮小增量直至為1，最后使用直接插入排序完成排序牵啦。
package com;
/*
* Java實(shí)現(xiàn)希爾排序（縮小增量排序）
* author:wyr
* 2016-7-14
*兩個(gè)步驟：1亚情，建堆 2，對頂與堆的最后一個(gè)元素交換位置
*/
public class ShellSort {
public static void main(String[] args) {
int a[] = {3,1,5,7,2,4,9,6,10,8};
ShellSort obj=new ShellSort();
System.out.println("初始值：");
obj.print(a);
obj.shellSort(a);
System.out.println("\n排序后：");
obj.print(a);
}
private void shellSort(int[] a) {
int dk = a.length/2;
while( dk >= 1 ){
ShellInsertSort(a, dk);
dk = dk/2;
}
}
private void ShellInsertSort(int[] a, int dk) {//類似插入排序哈雏，只是插入排序增量是1楞件，這里增量是dk,把1換成dk就可以了
for(int i=dk;i<a.length;i++){
if(a[i]<a[i-dk]){
int j;
int x=a[i];//x為待插入元素
a[i]=a[i-dk];
for(j=i-dk; j>=0 && x<a[j];j=j-dk){//通過循環(huán)衫生，逐個(gè)后移一位找到要插入的位置。
a[j+dk]=a[j];
}
a[j+dk]=x;//插入
}
}
}
public void print(int a[]){
for(int i=0;i<a.length;i++){
System.out.print(a[i]+" ");
}
}
}
希爾排序時(shí)效分析很難土浸，關(guān)鍵碼的比較次數(shù)與記錄移動(dòng)次數(shù)依賴于增量因子序列d的選取罪针，特定情況下可以準(zhǔn)確估算出關(guān)鍵碼的比較次數(shù)和記錄的移動(dòng)次數(shù)。目前還沒有人給出選取最好的增量因子序列的方法黄伊。增量因子序列可以有各種取法泪酱，有取奇數(shù)的，也有取質(zhì)數(shù)的还最，但需要注意：增量因子中除1 外沒有公因子墓阀，且最后一個(gè)增量因子必須為1。希爾排序方法是一個(gè)不穩(wěn)定的排序方法拓轻。
- 選擇排序—簡單選擇排序（Simple Selection Sort）
基本思想：
在要排序的一組數(shù)中斯撮，選出最小（或者最大）的一個(gè)數(shù)與第1個(gè)位置的數(shù)交換悦即；然后在剩下的數(shù)當(dāng)中再找最兴背伞（或者最大）的與第2個(gè)位置的數(shù)交換，依次類推辜梳，直到第n-1個(gè)元素（倒數(shù)第二個(gè)數(shù)）和第n個(gè)元素（最后一個(gè)數(shù)）比較為止粱甫。
簡單選擇排序的示例：
操作方法：
第一趟，從n 個(gè)記錄中找出關(guān)鍵碼最小的記錄與第一個(gè)記錄交換作瞄；
第二趟茶宵，從第二個(gè)記錄開始的n-1 個(gè)記錄中再選出關(guān)鍵碼最小的記錄與第二個(gè)記錄交換；
以此類推.....
第i 趟宗挥，則從第i 個(gè)記錄開始的n-i+1 個(gè)記錄中選出關(guān)鍵碼最小的記錄與第i 個(gè)記錄交換乌庶，
直到整個(gè)序列按關(guān)鍵碼有序。
算法實(shí)現(xiàn)：
package com;
/*
* Java實(shí)現(xiàn)希爾排序（縮小增量排序）
* author:wyr
* 2016-7-14
*兩個(gè)步驟：1契耿，建堆 2瞒大，對頂與堆的最后一個(gè)元素交換位置
*/
public class SimpleSelectSort {
public static void main(String[] args) {
int a[] = {3,1,5,7,2,4,9,6,10,8};
SimpleSelectSort obj=new SimpleSelectSort();
System.out.println("初始值：");
obj.print(a);
obj.selectSort(a);
System.out.println("\n排序后：");
obj.print(a);
}
private void selectSort(int[] a) {
for(int i=0;i<a.length;i++){
int k=i;//k存放最小值下標(biāo)。每次循環(huán)最小值下標(biāo)+1
for(int j=i+1;j<a.length;j++){//找到最小值下標(biāo)
if(a[k]>a[j])
k=j;
}
swap(a,k,i);//把最小值放到它該放的位置上
}
}
public void print(int a[]){
for(int i=0;i<a.length;i++){
System.out.print(a[i]+" ");
}
}
public void swap(int[] data, int i, int j) {
if (i == j) {
return;
}
data[i] = data[i] + data[j];
data[j] = data[i] - data[j];
data[i] = data[i] - data[j];
}
}
簡單選擇排序的改進(jìn)——二元選擇排序
簡單選擇排序搪桂，每趟循環(huán)只能確定一個(gè)元素排序后的定位透敌。我們可以考慮改進(jìn)為每趟循環(huán)確定兩個(gè)元素（當(dāng)前趟最大和最小記錄）的位置,從而減少排序所需的循環(huán)次數(shù)。改進(jìn)后對n個(gè)數(shù)據(jù)進(jìn)行排序踢械，最多只需進(jìn)行[n/2]趟循環(huán)即可酗电。具體實(shí)現(xiàn)如下：
void SelectSort(int r[],int n) {
int i ,j , min ,max, tmp;
for (i=1 ;i <= n/2;i++) {
// 做不超過n/2趟選擇排序
min = i; max = i ; //分別記錄最大和最小關(guān)鍵字記錄位置
for (j= i+1; j<= n-i; j++) {
if (r[j] > r[max]) {
max = j ; continue ;
}
if (r[j]< r[min]) {
min = j ;
}
}
//該交換操作還可分情況討論以提高效率
tmp = r[i-1]; r[i-1] = r[min]; r[min] = tmp;
tmp = r[n-i]; r[n-i] = r[max]; r[max] = tmp;
}
}
- 選擇排序—堆排序（Heap Sort）
堆排序是一種樹形選擇排序，是對直接選擇排序的有效改進(jìn)内列。基本思想：
堆的定義如下：具有n個(gè)元素的序列（k1,k2,...,kn),當(dāng)且僅當(dāng)滿足
時(shí)稱之為堆撵术。由堆的定義可以看出，堆頂元素（即第一個(gè)元素）必為最小項(xiàng)（小頂堆）话瞧。若以一維數(shù)組存儲一個(gè)堆嫩与，則堆對應(yīng)一棵完全二叉樹寝姿，且所有非葉結(jié)點(diǎn)的值均不大于(或不小于)其子女的值，根結(jié)點(diǎn)（堆頂元素）的值是最小(或最大)的划滋。如：
（a）大頂堆序列：（96, 83,27,38,11,09)
(b) 小頂堆序列：（12会油，36，24古毛，85，47都许，30稻薇，53，91）
初始時(shí)把要排序的n個(gè)數(shù)的序列看作是一棵順序存儲的二叉樹（一維數(shù)組存儲二叉樹）胶征，調(diào)整它們的存儲序塞椎，使之成為一個(gè)堆，將堆頂元素輸出睛低，得到n 個(gè)元素中最小(或最大)的元素案狠，這時(shí)堆的根節(jié)點(diǎn)的數(shù)最小（或者最大）钱雷。然后對前面(n-1)個(gè)元素重新調(diào)整使之成為堆骂铁，輸出堆頂元素，得到n 個(gè)元素中次小(或次大)的元素罩抗。依此類推拉庵，直到只有兩個(gè)節(jié)點(diǎn)的堆，并對它們作交換套蒂，最后得到有n個(gè)節(jié)點(diǎn)的有序序列钞支。稱這個(gè)過程為堆排序。
因此操刀，實(shí)現(xiàn)堆排序需解決兩個(gè)問題：1. 如何將n 個(gè)待排序的數(shù)建成堆烁挟；2. 輸出堆頂元素后，怎樣調(diào)整剩余n-1 個(gè)元素骨坑，使其成為一個(gè)新堆撼嗓。
首先討論第二個(gè)問題：輸出堆頂元素后，對剩余n-1元素重新建成堆的調(diào)整過程卡啰。調(diào)整小頂堆的方法：
1）設(shè)有m 個(gè)元素的堆静稻，輸出堆頂元素后，剩下m-1 個(gè)元素匈辱。將堆底元素送入堆頂（（最后一個(gè)元素與堆頂進(jìn)行交換）振湾，堆被破壞，其原因僅是根結(jié)點(diǎn)不滿足堆的性質(zhì)亡脸。
2）將根結(jié)點(diǎn)與左押搪、右子樹中較小元素的進(jìn)行交換树酪。
3）若與左子樹交換：如果左子樹堆被破壞，即左子樹的根結(jié)點(diǎn)不滿足堆的性質(zhì)大州，則重復(fù)方法 （2）.
4）若與右子樹交換续语，如果右子樹堆被破壞，即右子樹的根結(jié)點(diǎn)不滿足堆的性質(zhì)厦画。則重復(fù)方法 （2）.
5）繼續(xù)對不滿足堆性質(zhì)的子樹進(jìn)行上述交換操作疮茄，直到葉子結(jié)點(diǎn)，堆被建成根暑。
稱這個(gè)自根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的調(diào)整過程為篩選力试。如圖：
再討論對n 個(gè)元素初始建堆的過程。建堆方法：對初始序列建堆的過程排嫌，就是一個(gè)反復(fù)進(jìn)行篩選的過程畸裳。
1）n 個(gè)結(jié)點(diǎn)的完全二叉樹，則最后一個(gè)結(jié)點(diǎn)是第
2）篩選從第
3）之后向前依次對各結(jié)點(diǎn)為根的子樹進(jìn)行篩選颇象，使之成為堆伍伤，直到根結(jié)點(diǎn)。
如圖建堆初始過程：無序序列：（49夯到，38嚷缭，65，97耍贾，76阅爽，13，27荐开，49）
** 算法的實(shí)現(xiàn)：**
從算法描述來看付翁，堆排序需要兩個(gè)過程，一是建立堆晃听，二是堆頂與堆的最后一個(gè)元素交換位置百侧。所以堆排序有兩個(gè)函數(shù)組成。一是建堆的滲透函數(shù)能扒，二是反復(fù)調(diào)用滲透函數(shù)實(shí)現(xiàn)排序的函數(shù)佣渴。
package com;
/*
* Java實(shí)現(xiàn)快速排序算法
* 由大到小排序
* author:wyr
* 2016-7-14
*兩個(gè)步驟：1，建堆 2初斑，對頂與堆的最后一個(gè)元素交換位置
*/
public class HeapSort {
public static void main(String[] args) {
int a[] = {3,1,5,7,2,4,9,6,10,8};
HeapSort obj=new HeapSort();
System.out.println("初始值：");
obj.print(a);
for(int i=0;i<a.length;i++){
obj.createLittleHeap(a,a.length-1-i);//創(chuàng)建堆,創(chuàng)建的是小頂堆辛润。每次循環(huán)完，二叉樹的根節(jié)點(diǎn)都是最小值见秤，所以與此時(shí)的未排好部分最后一個(gè)值交換位置
obj.swap(a, 0, a.length - 1 - i);//與最后一個(gè)值交換位置砂竖，最小值找到了位置
obj.print(a);
System.out.println();
}
System.out.println("\n排序后：");
obj.print(a);
}
/*
* 創(chuàng)建小頂堆：雙親節(jié)點(diǎn)小于子節(jié)點(diǎn)的值真椿。從葉子節(jié)點(diǎn)開始，直到根節(jié)點(diǎn)乎澄。這樣建立的堆定位最小值
*/
private void createLittleHeap(int[] data, int last) {
for (int i = (last- 1) / 2; i >= 0; i--) { //找到最后一個(gè)葉子節(jié)點(diǎn)的雙親節(jié)點(diǎn)
// 保存當(dāng)前正在判斷的節(jié)點(diǎn)
int parent = i;
// 若當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)存在突硝，即子節(jié)點(diǎn)存在
while (2 * parent + 1 <= last) {
// biggerIndex總是記錄較大節(jié)點(diǎn)的值,先賦值為當(dāng)前判斷節(jié)點(diǎn)的左子節(jié)點(diǎn)
int bigger = 2 * parent + 1;//bigger指向左子節(jié)點(diǎn)
if (bigger < last) { //說明存在右子節(jié)點(diǎn)
if (data[bigger] > data[bigger+ 1]) { //右子節(jié)點(diǎn)>左子節(jié)點(diǎn)時(shí)
bigger=bigger+1;
}
}
if (data[parent] > data[bigger]) { //若雙親節(jié)點(diǎn)值大于子節(jié)點(diǎn)中最大的
// 若當(dāng)前節(jié)點(diǎn)值比子節(jié)點(diǎn)最大值小，則交換2者得值置济，交換后將biggerIndex值賦值給k
swap(data, parent, bigger);
parent = bigger;
} else {
break;
}
}
}
}
public void print(int a[]){
for(int i=0;i<a.length;i++){
System.out.print(a[i]+" ");
}
}
public void swap(int[] data, int i, int j) {
if (i == j) {
return;
}
data[i] = data[i] + data[j];
data[j] = data[i] - data[j];
data[i] = data[i] - data[j];
}
}
堆排序需要雙層循環(huán)解恰，第一層控制循環(huán)多少次，第二層得到每次的最小值（小頂堆）
package arrayTest;
import java.util.ArrayList;
public class Solution32 {
/* 輸入n個(gè)整數(shù)浙于，找出其中最小的K個(gè)數(shù)修噪。
* 例如輸入4,5,1,6,2,7,3,8這8個(gè)數(shù)字，
* 則最小的4個(gè)數(shù)字是1,2,3,4,路媚。
* */
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> result = new ArrayList<Integer>();
if(k > input.length) return result;
for(int i = 0; i < k ; i ++){//只排前k次
heapSort(input,i,input.length);//進(jìn)行第i次排序
result.add(input[i]);
}
return result;
}
private void heapSort( int [] input, int root, int end){//小頂堆實(shí)現(xiàn)
for(int j = end -1; j >= root; j --){
int parent = (j + root -1)/2;//算出j節(jié)點(diǎn)的雙親節(jié)點(diǎn)的序號
if(input[parent] > input[j]){//雙親節(jié)點(diǎn)大于當(dāng)前節(jié)點(diǎn)，交換位置樊销。
int temp = input[j];
input[j] = input[parent];
input[parent] = temp;
}
}
}
public static void main(String[] args) {
int [] str={4,5,1,6,2,7,3,8};
Solution32 s=new Solution32();
System.out.print(s.GetLeastNumbers_Solution(str,4));
}
}
**分析:******
而建堆時(shí)的比較次數(shù)不超過4n 次，因此堆排序最壞情況下腺占，時(shí)間復(fù)雜度也為：O(nlogn )淤袜。
- 交換排序—冒泡排序（Bubble Sort）
基本思想：
在要排序的一組數(shù)中，對當(dāng)前還未排好序的范圍內(nèi)的全部數(shù)衰伯，自上而下對相鄰的兩個(gè)數(shù)依次進(jìn)行比較和調(diào)整铡羡，讓較大的數(shù)往下沉，較小的往上冒意鲸。即：每當(dāng)兩相鄰的數(shù)比較后發(fā)現(xiàn)它們的排序與排序要求相反時(shí)烦周，就將它們互換。
冒泡排序的示例：
算法的實(shí)現(xiàn)：
void bubbleSort(int a[], int n){
for(int i =0 ; i< n-1; ++i) {
for(int j = 0; j < n-i-1; ++j) {
if(a[j] > a[j+1])
{
int tmp = a[j] ; a[j] = a[j+1] ; a[j+1] = tmp;
}
}
}
}
冒泡排序算法的改進(jìn)
對冒泡排序常見的改進(jìn)方法是加入一標(biāo)志性變量exchange怎顾，用于標(biāo)志某一趟排序過程中是否有數(shù)據(jù)交換读慎，如果進(jìn)行某一趟排序時(shí)并沒有進(jìn)行數(shù)據(jù)交換，則說明數(shù)據(jù)已經(jīng)按要求排列好槐雾，可立即結(jié)束排序夭委，避免不必要的比較過程。本文再提供以下兩種改進(jìn)算法：
1．設(shè)置一標(biāo)志性變量pos,用于記錄每趟排序中最后一次進(jìn)行交換的位置蚜退。由于pos位置之后的記錄均已交換到位,故在進(jìn)行下一趟排序時(shí)只要掃描到pos位置即可闰靴。
改進(jìn)后算法如下:
void Bubble_1 ( int r[], int n) {
int i= n -1; //初始時(shí),最后位置保持不變
while ( i> 0) {
int pos= 0; //每趟開始時(shí),無記錄交換
for (int j= 0; j< i; j++)
if (r[j]> r[j+1]) {
pos= j; //記錄交換的位置
int tmp = r[j]; r[j]=r[j+1];r[j+1]=tmp;
}
i= pos; //為下一趟排序作準(zhǔn)備
}
}
2．傳統(tǒng)冒泡排序中每一趟排序操作只能找到一個(gè)最大值或最小值,我們考慮利用在每趟排序中進(jìn)行正向和反向兩遍冒泡的方法一次可以得到兩個(gè)最終值(最大者和最小者) , 從而使排序趟數(shù)幾乎減少了一半彪笼。
改進(jìn)后的算法實(shí)現(xiàn)為:
void Bubble_2 ( int r[], int n){
int low = 0;
int high= n -1; //設(shè)置變量的初始值
int tmp,j;
while (low < high) {
for (j= low; j< high; ++j) //正向冒泡,找到最大者
if (r[j]> r[j+1]) {
tmp = r[j]; r[j]=r[j+1];r[j+1]=tmp;
}
--high; //修改high值, 前移一位
for ( j=high; j>low; --j) //反向冒泡,找到最小者
if (r[j]<r[j-1]) {
tmp = r[j]; r[j]=r[j-1];r[j-1]=tmp;
}
++low; //修改low值,后移一位
}
}
- 交換排序—快速排序（Quick Sort）
基本思想：
1）選擇一個(gè)基準(zhǔn)元素,通常選擇第一個(gè)元素或者最后一個(gè)元素,
2）通過一趟排序講待排序的記錄分割成獨(dú)立的兩部分，其中一部分記錄的元素值均比基準(zhǔn)元素值小蚂且。另一部分記錄的 元素值比基準(zhǔn)值大配猫。
3）此時(shí)基準(zhǔn)元素在其排好序后的正確位置
4）然后分別對這兩部分記錄用同樣的方法繼續(xù)進(jìn)行排序，直到整個(gè)序列有序杏死。
快速排序的示例：
（a）一趟排序的過程：
（b）排序的全過程
算法的實(shí)現(xiàn)：
遞歸實(shí)現(xiàn)：
package com;
/*
* Java實(shí)現(xiàn)快速排序算法
* author:wyr
* 2016-7-14
*/
public class QuickSort {
public static void main(String[] args) {
int a[] = {3,1,5,7,2,4,9,6,10,8};
QuickSort obj=new QuickSort();
System.out.println("初始值：");
obj.print(a);
int h=a.length-1;
obj.quickSort(a,0,h);
System.out.println("\n排序后：");
obj.print(a);
}
private void quickSort(int[] a,int low, int high) {
if(low<high){ //如果不加這個(gè)判斷遞歸會(huì)無法退出導(dǎo)致堆棧溢出異常
int middle=getMiddle(a,low,high);
quickSort(a, 0, middle-1); //遞歸對低子表遞歸排序
quickSort(a, middle + 1, high); //遞歸對高子表遞歸排序
}
}
public int getMiddle(int[] a, int low, int high){
int key = a[low];//基準(zhǔn)元素泵肄，排序中會(huì)空出來一個(gè)位置
while(low<high){
while(low<high && a[high]>=key){//從high開始找比基準(zhǔn)小的，與low換位置
high--;
}
a[low]=a[high];
while(low<high && a[low]<=key){//從low開始找比基準(zhǔn)大,放到之前high空出來的位置上
low++;
}
a[high]=a[low];
}
a[low]=key;//此時(shí)low=high 是基準(zhǔn)元素的位置淑翼，也是空出來的那個(gè)位置
return low;
}
public void print(int a[]){
for(int i=0;i<a.length;i++){
System.out.print(a[i]+" ");
}
}
}
分析：
快速排序是通常被認(rèn)為在同數(shù)量級（O(nlog2n)）的排序方法中平均性能最好的腐巢。但若初始序列按關(guān)鍵碼有序或基本有序時(shí)，快排序反而蛻化為冒泡排序玄括。為改進(jìn)之冯丙，通常以“三者取中法”來選取基準(zhǔn)記錄，即將排序區(qū)間的兩個(gè)端點(diǎn)與中點(diǎn)三個(gè)記錄關(guān)鍵碼居中的調(diào)整為支點(diǎn)記錄遭京∥赶В快速排序是一個(gè)不穩(wěn)定的排序方法。
快速排序的改進(jìn)
在本改進(jìn)算法中,只對長度大于k的子序列遞歸調(diào)用快速排序,讓原序列基本有序哪雕，然后再對整個(gè)基本有序序列用插入排序算法排序船殉。實(shí)踐證明，改進(jìn)后的算法時(shí)間復(fù)雜度有所降低斯嚎，且當(dāng)k取值為 8 左右時(shí),改進(jìn)算法的性能最佳利虫。算法思想如下：
void print(int a[], int n){
for(int j= 0; j<n; j++){
cout<<a[j] <<" ";
}
cout<<endl;
}
void swap(int *a, int *b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
int partition(int a[], int low, int high)
{
int privotKey = a[low]; //基準(zhǔn)元素
while(low < high){ //從表的兩端交替地向中間掃描
while(low < high && a[high] >= privotKey) --high; //從high 所指位置向前搜索，至多到low+1 位置堡僻。將比基準(zhǔn)元素小的交換到低端
swap(&a[low], &a[high]);
while(low < high && a[low] <= privotKey ) ++low;
swap(&a[low], &a[high]);
}
print(a,10);
return low;
}
void qsort_improve(int r[ ],int low,int high, int k){
if( high -low > k ) { //長度大于k時(shí)遞歸, k為指定的數(shù)
int pivot = partition(r, low, high); // 調(diào)用的Partition算法保持不變
qsort_improve(r, low, pivot - 1,k);
qsort_improve(r, pivot + 1, high,k);
}
}
void quickSort(int r[], int n, int k){
qsort_improve(r,0,n,k);//先調(diào)用改進(jìn)算法Qsort使之基本有序
//再用插入排序?qū)居行蛐蛄信判?
for(int i=1; i<=n;i ++){
int tmp = r[i];
int j=i-1;
while(tmp < r[j]){
r[j+1]=r[j]; j=j-1;
}
r[j+1] = tmp;
}
}
int main(){
int a[10] = {3,1,5,7,2,4,9,6,10,8};
cout<<"初始值：";
print(a,10);
quickSort(a,9,4);
cout<<"結(jié)果：";
print(a,10);
}
- 歸并排序（Merge Sort）
基本思想：
歸并（Merge）排序法是將兩個(gè)（或兩個(gè)以上）有序表合并成一個(gè)新的有序表糠惫，即把待排序序列分為若干個(gè)子序列，每個(gè)子序列是有序的钉疫。然后再把有序子序列合并為整體有序序列寞钥。
歸并排序示例：
合并方法：
設(shè)r[i…n]由兩個(gè)有序子表r[i…m]和r[m+1…n]組成，兩個(gè)子表長度分別為n-i +1陌选、n-m理郑。
j=m+1；k=i咨油；i=i; //置兩個(gè)子表的起始下標(biāo)及輔助數(shù)組的起始下標(biāo)
若i>m 或j>n您炉，轉(zhuǎn)⑷ //其中一個(gè)子表已合并完，比較選取結(jié)束
//選取r[i]和r[j]較小的存入輔助數(shù)組rf如果r[i]<r[j]役电，rf[k]=r[i]赚爵； i++； k++； 轉(zhuǎn)⑵否則冀膝，rf[k]=r[j]唁奢； j++； k++窝剖； 轉(zhuǎn)⑵
//將尚未處理完的子表中元素存入rf如果i<=m麻掸，將r[i…m]存入rf[k…n] //前一子表非空如果j<=n , 將r[j…n] 存入rf[k…n] //后一子表非空
合并結(jié)束。
[cpp] view plain copy
//將r[i…m]和r[m +1 …n]歸并到輔助數(shù)組rf[i…n]
void Merge(ElemType *r,ElemType *rf, int i, int m, int n)
{
int j,k;
for(j=m+1,k=i; i<=m && j <=n ; ++k){
if(r[j] < r[i]) rf[k] = r[j++];
else rf[k] = r[i++];
}
while(i <= m) rf[k++] = r[i++];
while(j <= n) rf[k++] = r[j++];
}
歸并的迭代算法
1 個(gè)元素的表總是有序的赐纱。所以對n 個(gè)元素的待排序列脊奋，每個(gè)元素可看成1 個(gè)有序子表。對子表兩兩合并生成n/2個(gè)子表疙描，所得子表除最后一個(gè)子表長度可能為1 外诚隙，其余子表長度均為2。再進(jìn)行兩兩合并起胰，直到生成n 個(gè)元素按關(guān)鍵碼有序的表久又。
void print(int a[], int n){
for(int j= 0; j<n; j++){
cout<<a[j] <<" ";
}
cout<<endl;
}
//將r[i…m]和r[m +1 …n]歸并到輔助數(shù)組rf[i…n]
void Merge(ElemType *r,ElemType *rf, int i, int m, int n)
{
int j,k;
for(j=m+1,k=i; i<=m && j <=n ; ++k){
if(r[j] < r[i]) rf[k] = r[j++];
else rf[k] = r[i++];
}
while(i <= m) rf[k++] = r[i++];
while(j <= n) rf[k++] = r[j++];
print(rf,n+1);
}
void MergeSort(ElemType *r, ElemType *rf, int lenght)
{
int len = 1;
ElemType *q = r ;
ElemType *tmp ;
while(len < lenght) {
int s = len;
len = 2 * s ;
int i = 0;
while(i+ len <lenght){
Merge(q, rf, i, i+ s-1, i+ len-1 ); //對等長的兩個(gè)子表合并
i = i+ len;
}
if(i + s < lenght){
Merge(q, rf, i, i+ s -1, lenght -1); //對不等長的兩個(gè)子表合并
}
tmp = q; q = rf; rf = tmp; //交換q,rf，以保證下一趟歸并時(shí)效五，仍從q 歸并到rf
}
}
int main(){
int a[10] = {3,1,5,7,2,4,9,6,10,8};
int b[10];
MergeSort(a, b, 10);
print(b,10);
cout<<"結(jié)果：";
print(a,10);
}
**兩路歸并的遞歸算法**
**[cpp]** [view plain](http://blog.csdn.net/hguisu/article/details/7776068#) [copy](http://blog.csdn.net/hguisu/article/details/7776068#)
void MSort(ElemType *r, ElemType *rf,int s, int t)
{
ElemType *rf2;
if(s==t) r[s] = rf[s];
else
{
int m=(s+t)/2; /*平分*p 表*/
MSort(r, rf2, s, m); /*遞歸地將p[s…m]歸并為有序的p2[s…m]*/
MSort(r, rf2, m+1, t); /*遞歸地將p[m+1…t]歸并為有序的p2[m+1…t]*/
Merge(rf2, rf, s, m+1,t); /*將p2[s…m]和p2[m+1…t]歸并到p1[s…t]*/
}
}
void MergeSort_recursive(ElemType *r, ElemType *rf, int n)
{ /*對順序表*p 作歸并排序*/
MSort(r, rf,0, n-1);
}
- 桶排序/基數(shù)排序(Radix Sort)
說基數(shù)排序之前籽孙，我們先說桶排序：
基本思想：是將陣列分到有限數(shù)量的桶子里。每個(gè)桶子再個(gè)別排序（有可能再使用別的排序算法或是以遞回方式繼續(xù)使用桶排序進(jìn)行排序）火俄。桶排序是鴿巢排序的一種歸納結(jié)果。當(dāng)要被排序的陣列內(nèi)的數(shù)值是均勻分配的時(shí)候讲冠，桶排序使用線性時(shí)間（Θ（n））瓜客。但桶排序并不是 比較排序，他不受到 O(n log n) 下限的影響竿开。 簡單來說谱仪，就是把數(shù)據(jù)分組，放在一個(gè)個(gè)的桶中否彩，然后對每個(gè)桶里面的在進(jìn)行排序疯攒。
例如要對大小為[1..1000]范圍內(nèi)的n個(gè)整數(shù)A[1..n]排序
首先，可以把桶設(shè)為大小為10的范圍列荔，具體而言敬尺，設(shè)集合B[1]存儲[1..10]的整數(shù)，集合B[2]存儲 (10..20]的整數(shù)贴浙，……集合B[i]存儲( (i-1)10, i10]的整數(shù)砂吞，i = 1,2,..100∑槔＃總共有 100個(gè)桶蜻直。
然后，對A[1..n]從頭到尾掃描一遍，把每個(gè)A[i]放入對應(yīng)的桶B[j]中概而。 再對這100個(gè)桶中每個(gè)桶里的數(shù)字排序呼巷，這時(shí)可用冒泡，選擇赎瑰，乃至快排王悍，一般來說任 何排序法都可以。
最后乡范，依次輸出每個(gè)桶里面的數(shù)字配名，且每個(gè)桶中的數(shù)字從小到大輸出，這 樣就得到所有數(shù)字排好序的一個(gè)序列了晋辆。
假設(shè)有n個(gè)數(shù)字渠脉，有m個(gè)桶，如果數(shù)字是平均分布的瓶佳，則每個(gè)桶里面平均有n/m個(gè)數(shù)字芋膘。如果
對每個(gè)桶中的數(shù)字采用快速排序，那么整個(gè)算法的復(fù)雜度是
O(n + m * n/mlog(n/m)) = O(n + nlogn - nlogm)
從上式看出霸饲，當(dāng)m接近n的時(shí)候为朋，桶排序復(fù)雜度接近O(n)
當(dāng)然，以上復(fù)雜度的計(jì)算是基于輸入的n個(gè)數(shù)字是平均分布這個(gè)假設(shè)的厚脉。這個(gè)假設(shè)是很強(qiáng)的 习寸，實(shí)際應(yīng)用中效果并沒有這么好。如果所有的數(shù)字都落在同一個(gè)桶中傻工，那就退化成一般的排序了霞溪。
前面說的幾大排序算法* ，大部分時(shí)間復(fù)雜度都是O（n2）中捆，也有部分排序算法時(shí)間復(fù)雜度是O(nlogn)鸯匹。而桶式排序卻能實(shí)現(xiàn)O（n）的時(shí)間復(fù)雜度。但桶排序的缺點(diǎn)是：
1）首先是空間復(fù)雜度比較高泄伪，需要的額外開銷大殴蓬。排序有兩個(gè)數(shù)組的空間開銷，一個(gè)存放待排序數(shù)組蟋滴，一個(gè)就是所謂的桶染厅，比如待排序值是從0到m-1，那就需要m個(gè)桶津函，這個(gè)桶數(shù)組就要至少m個(gè)空間糟秘。
2）其次待排序的元素都要在一定的范圍內(nèi)等等。
桶式排序是一種分配排序球散。分配排序的特定是不需要進(jìn)行關(guān)鍵碼的比較尿赚，但前提是要知道待排序列的一些具體情況散庶。
分配排序的基本思想：說白了就是進(jìn)行多次的桶式排序。****
基數(shù)排序過程無須比較關(guān)鍵字凌净，而是通過“分配”和“收集”過程來實(shí)現(xiàn)排序悲龟。它們的時(shí)間復(fù)雜度可達(dá)到線性階：O(n)。
實(shí)例:
撲克牌中52 張牌冰寻，可按花色和面值分成兩個(gè)字段须教，其大小關(guān)系為：花色： 梅花< 方塊< 紅心< 黑心
若對撲克牌按花色、面值進(jìn)行升序排序斩芭，得到如下序列：
即兩張牌轻腺，若花色不同，不論面值怎樣划乖，花色低的那張牌小于花色高的贬养，只有在同花色情況下，大小關(guān)系才由面值的大小確定琴庵。這就是多關(guān)鍵碼排序误算。
為得到排序結(jié)果，我們討論兩種排序方法迷殿。方法1：先對花色排序儿礼，將其分為4 個(gè)組，即梅花組庆寺、方塊組蚊夫、紅心組、黑心組懦尝。再對每個(gè)組分別按面值進(jìn)行排序知纷，最后，將4 個(gè)組連接起來即可导披。方法2：先按13 個(gè)面值給出13 個(gè)編號組(2 號，3 號埃唯，...撩匕，A 號)，將牌按面值依次放入對應(yīng)的編號組墨叛，分成13 堆止毕。再按花色給出4 個(gè)編號組(梅花、方塊漠趁、紅心扁凛、黑心)，將2號組中牌取出分別放入對應(yīng)花色組闯传，再將3 號組中牌取出分別放入對應(yīng)花色組谨朝，……，這樣，4 個(gè)花色組中均按面值有序字币，然后则披，將4 個(gè)花色組依次連接起來即可。
設(shè)n 個(gè)元素的待排序列包含d 個(gè)關(guān)鍵碼{k1洗出，k2士复，…，kd}翩活，則稱序列對關(guān)鍵碼{k1阱洪，k2，…菠镇，kd}有序是指：對于序列中任兩個(gè)記錄r[i]和rj都滿足下列有序關(guān)系：
其中k1 稱為最主位關(guān)鍵碼冗荸，kd 稱為最次位關(guān)鍵碼 。
兩種多關(guān)鍵碼排序方法：
多關(guān)鍵碼排序按照從最主位關(guān)鍵碼到最次位關(guān)鍵碼或從最次位到最主位關(guān)鍵碼的順序逐次排序辟犀，分兩種方法：
最高位優(yōu)先(Most Significant Digit first)法俏竞，簡稱MSD 法：
1）先按k1 排序分組，將序列分成若干子序列堂竟，同一組序列的記錄中魂毁，關(guān)鍵碼k1 相等。
2）再對各組按k2 排序分成子組出嘹，之后席楚，對后面的關(guān)鍵碼繼續(xù)這樣的排序分組，直到按最次位關(guān)鍵碼kd 對各子組排序后税稼。
3）再將各組連接起來烦秩，便得到一個(gè)有序序列。撲克牌按花色郎仆、面值排序中介紹的方法一即是MSD 法只祠。
最低位優(yōu)先(Least Significant Digit first)法，簡稱LSD 法：
- 先從kd 開始排序扰肌，再對kd-1進(jìn)行排序抛寝，依次重復(fù)，直到按k1排序分組分成最小的子序列后曙旭。
- 最后將各個(gè)子序列連接起來盗舰，便可得到一個(gè)有序的序列, 撲克牌按花色、面值排序中介紹的方法二即是LSD 法桂躏。
基于LSD方法的鏈?zhǔn)交鶖?shù)排序的基本思想
“多關(guān)鍵字排序”的思想實(shí)現(xiàn)“單關(guān)鍵字排序”钻趋。對數(shù)字型或字符型的單關(guān)鍵字，可以看作由多個(gè)數(shù)位或多個(gè)字符構(gòu)成的多關(guān)鍵字剂习，此時(shí)可以采用“分配-收集”的方法進(jìn)行排序蛮位，這一過程稱作基數(shù)排序法较沪，其中每個(gè)數(shù)字或字符可能的取值個(gè)數(shù)稱為基數(shù)。比如土至，撲克牌的花色基數(shù)為4购对，面值基數(shù)為13。在整理撲克牌時(shí)陶因，既可以先按花色整理骡苞，也可以先按面值整理。按花色整理時(shí)楷扬，先按紅解幽、黑、方烘苹、花的順序分成4摞（分配）躲株，再按此順序再疊放在一起（收集），然后按面值的順序分成13摞（分配）镣衡，再按此順序疊放在一起（收集）霜定，如此進(jìn)行二次分配和收集即可將撲克牌排列有序。
基數(shù)排序:
是按照低位先排序廊鸥，然后收集望浩；再按照高位排序，然后再收集惰说；依次類推磨德，直到最高位。有時(shí)候有些屬性是有優(yōu)先級順序的吆视，先按低優(yōu)先級排序典挑，再按高優(yōu)先級排序。最后的次序就是高優(yōu)先級高的在前啦吧，高優(yōu)先級相同的低優(yōu)先級高的在前您觉。基數(shù)排序基于分別排序授滓，分別收集琳水，所以是穩(wěn)定的。
算法實(shí)現(xiàn)：
Void RadixSort(Node L[],length,maxradix)
{
int m,n,k,lsp;
k=1;m=1;
int temp[10][length-1];
Empty(temp); //清空臨時(shí)空間
while(k<maxradix) //遍歷所有關(guān)鍵字
{
for(int i=0;i<length;i++) //分配過程
{
if(L[i]<m)
Temp[0][n]=L[i];
else
Lsp=(L[i]/m)%10; //確定關(guān)鍵字
Temp[lsp][n]=L[i];
n++;
}
CollectElement(L,Temp); //收集
n=0;
m=m*10;
k++;
}
}
總結(jié)
各種排序的穩(wěn)定性褒墨，時(shí)間復(fù)雜度和空間復(fù)雜度總結(jié)：
我們比較時(shí)間復(fù)雜度函數(shù)的情況：
時(shí)間復(fù)雜度函數(shù)O(n)的增長情況
所以對n較大的排序記錄炫刷。一般的選擇都是時(shí)間復(fù)雜度為O(nlog2n)的排序方法擎宝。
時(shí)間復(fù)雜度來說：
(1)平方階(O(n2
))排序 各類簡單排序:直接插入郁妈、直接選擇和冒泡排序； (2)線性對數(shù)階(O(nlog2n))排序 快速排序、堆排序和歸并排序； (3)O(n1+§
))排序,§是介于0和1之間的常數(shù)淆攻。
希爾排序(4)線性階(O(n))排序 基數(shù)排序避凝，此外還有桶双吆、箱排序陆爽。
說明：
當(dāng)原表有序或基本有序時(shí)缸废，直接插入排序和冒泡排序?qū)⒋蟠鬁p少比較次數(shù)和移動(dòng)記錄的次數(shù)同云，時(shí)間復(fù)雜度可降至O（n）仆百；
而快速排序則相反厕隧，當(dāng)原表基本有序時(shí)，將蛻化為冒泡排序俄周，時(shí)間復(fù)雜度提高為O（n2）吁讨；
原表是否有序，對簡單選擇排序峦朗、堆排序建丧、歸并排序和基數(shù)排序的時(shí)間復(fù)雜度影響不大。
穩(wěn)定性：
排序算法的穩(wěn)定性:若待排序的序列中波势，存在多個(gè)具有相同關(guān)鍵字的記錄翎朱，經(jīng)過排序， 這些記錄的相對次序保持不變尺铣，則稱該算法是穩(wěn)定的拴曲；若經(jīng)排序后，記錄的相對 次序發(fā)生了改變迄埃，則稱該算法是不穩(wěn)定的疗韵。 穩(wěn)定性的好處：排序算法如果是穩(wěn)定的，那么從一個(gè)鍵上排序侄非，然后再從另一個(gè)鍵上排序蕉汪，第一個(gè)鍵排序的結(jié)果可以為第二個(gè)鍵排序所用〕言梗基數(shù)排序就是這樣者疤，先按低位排序，逐次按高位排序叠赦，低位相同的元素其順序再高位也相同時(shí)是不會(huì)改變的驹马。另外，如果排序算法穩(wěn)定除秀，可以避免多余的比較糯累；
穩(wěn)定的排序算法：冒泡排序、插入排序册踩、歸并排序和基數(shù)排序
不是穩(wěn)定的排序算法：選擇排序泳姐、快速排序、希爾排序暂吉、堆排序
選擇排序算法準(zhǔn)則：
每種排序算法都各有優(yōu)缺點(diǎn)胖秒。因此缎患，在實(shí)用時(shí)需根據(jù)不同情況適當(dāng)選用，甚至可以將多種方法結(jié)合起來使用阎肝。
選擇排序算法的依據(jù)
影響排序的因素有很多挤渔，平均時(shí)間復(fù)雜度低的算法并不一定就是最優(yōu)的。相反风题，有時(shí)平均時(shí)間復(fù)雜度高的算法可能更適合某些特殊情況判导。同時(shí)，選擇算法時(shí)還得考慮它的可讀性沛硅，以利于軟件的維護(hù)骡楼。一般而言，需要考慮的因素有以下四點(diǎn)：
1．待排序的記錄數(shù)目n的大谢蕖鸟整；
2．記錄本身數(shù)據(jù)量的大小，也就是記錄中除關(guān)鍵字外的其他信息量的大须獭篮条；
3．關(guān)鍵字的結(jié)構(gòu)及其分布情況；
4．對排序穩(wěn)定性的要求吩抓。
設(shè)待排序元素的個(gè)數(shù)為n.
1）當(dāng)n較大涉茧，則應(yīng)采用時(shí)間復(fù)雜度為O(nlog2n)的排序方法：快速排序、堆排序或歸并排序序疹娶。
快速排序：是目前基于比較的內(nèi)部排序中被認(rèn)為是最好的方法伴栓，當(dāng)待排序的關(guān)鍵字是隨機(jī)分布時(shí)，快速排序的平均時(shí)間最短雨饺； 堆排序 ： 如果內(nèi)存空間允許且要求穩(wěn)定性的钳垮，
歸并排序：它有一定數(shù)量的數(shù)據(jù)移動(dòng)，所以我們可能過與插入排序組合额港，先獲得一定長度的序列饺窿，然后再合并，在效率上將有所提高移斩。
2） 當(dāng)n較大肚医，內(nèi)存空間允許，且要求穩(wěn)定性 =》歸并排序
3）當(dāng)n較小向瓷，可采用直接插入或直接選擇排序肠套。
直接插入排序：當(dāng)元素分布有序，直接插入排序?qū)⒋蟠鬁p少比較次數(shù)和移動(dòng)記錄的次數(shù)猖任。
直接選擇排序 ：元素分布有序你稚，如果不要求穩(wěn)定性，選擇直接選擇排序
5）一般不使用或不直接使用傳統(tǒng)的冒泡排序。
6）基數(shù)排序它是一種穩(wěn)定的排序算法入宦，但有一定的局限性： 1、關(guān)鍵字可分解室琢∏颍 2、記錄的關(guān)鍵字位數(shù)較少盈滴，如果密集更好 3涯肩、如果是數(shù)字時(shí)，最好是無符號的巢钓，否則將增加相應(yīng)的映射復(fù)雜度病苗，可先將其正負(fù)分開排序。
注明：本人根據(jù)C++改的java算法
轉(zhuǎn)載請?zhí)崾境鎏帲?a target="_blank" rel="nofollow">http://blog.csdn.net/hguisu/article/details/7776068
