簡(jiǎn)單選擇排序
對(duì)于長(zhǎng)度為n的數(shù)組a
- 找出后n個(gè)數(shù)（下標(biāo)0~n-1）中最小的數(shù)熬芜，與a[0]交換
- 找出后n-1個(gè)數(shù)（下標(biāo)1~n-1）中最小的數(shù)，與a[1]交換
- 找出后n-2個(gè)數(shù)（下標(biāo)2~n-1）中最小的數(shù)，與a[2]交換
-
依次類推
即每次找到剩余數(shù)組中最小的元素放在前面，代碼如下：
/**
* 簡(jiǎn)單選擇排序，O（n^2）
* @param a
*/
public static void selectSort(int[] a) {
for (int i = 0; i < a.length-1; i++) {
int k=i; //剩余數(shù)組中最小元素下標(biāo)
for (int j = i+1; j < a.length; j++) {
if(a[k]>a[j])
k=j;
}
//交換a[k]與a[i]
swap(a, k, i);
}
}
冒泡排序
對(duì)于長(zhǎng)度為n的數(shù)組a
- 對(duì)前n個(gè)數(shù)進(jìn)行冒泡式交換（從0到n-1望门，如果相鄰的兩個(gè)數(shù)形娇，a[i]>a[i+1]則交換）锰霜，最后使a[n-1]為前n個(gè)數(shù)中最大數(shù)
- 對(duì)前n-1個(gè)數(shù)進(jìn)行冒泡式交換，最后使a[n-2]為前n-1個(gè)數(shù)中最大數(shù)
- 對(duì)前n-2個(gè)數(shù)進(jìn)行冒泡式交換桐早，最后使a[n-3]為前n-2個(gè)數(shù)中最大數(shù)
-
依次類推
即每次找出最大的數(shù)放在后面癣缅，與選擇排序相反。代碼如下：
/**
* 冒泡排序哄酝，O（n^2）
* @param a
*/
public static void bubbleSort(int[] a) {
for (int i = 0; i < a.length; i++) {
//一次排序后使尾部的數(shù)為最大的
for (int j = 0; j < a.length-i-1; j++) {
if(a[j]>a[j+1]){
swap(a, j, j+1);
}
}
}
}
插入排序
對(duì)于無(wú)序序列友存，假設(shè)前i個(gè)數(shù)為有序的，將第i+1個(gè)數(shù)插入前i個(gè)數(shù)中陶衅，使其成為i+1個(gè)有序序列屡立。
如圖，對(duì)于長(zhǎng)度為n的數(shù)組a
- 前1個(gè)數(shù)為有序序列搀军，將a[1]插入其中膨俐，形成2個(gè)數(shù)的有序序列
- 前2個(gè)數(shù)為有序序列，將a[2]插入其中罩句，形成3個(gè)數(shù)的有序序列
-
依次類推焚刺，最終前n個(gè)數(shù)都變成有序序列，排序成功
代碼如下：
/**
* 插入排序门烂，O（n^2）
* @param a
*/
public static void insertSort(int[] a) {
int temp,j;
//將a[i]插入前面的有序序列中
for (int i = 1; i < a.length; i++) {
temp=a[i];
//從有序序列尾部遞減乳愉，如果比a[i]大則向后放置
for (j=i-1; j >=0&&a[j]>temp; j--) {
a[j+1]=a[j];
}
//將a[i]插入有序序列
a[j+1]=temp;
}
}
快速排序
稍微復(fù)雜點(diǎn)的算法，運(yùn)用了“分治”的思想
對(duì)于無(wú)序序列屯远，隨便找出其中一個(gè)數(shù)作為“基準(zhǔn)數(shù)”蔓姚，然后將序列中小于它的數(shù)放在其左邊，大于它的數(shù)放在它右邊慨丐。再對(duì)左右區(qū)間重復(fù)此過程坡脐，直到區(qū)間只有一個(gè)數(shù)，排序成功咖气。具體過程如下圖：
過程很好理解挨措，但難點(diǎn)在于如何實(shí)現(xiàn)這個(gè)左右區(qū)間呢?
我們?cè)O(shè)置兩個(gè)變量i和j挖滤，分別指向序列的頭和尾。讓i遞增浅役，j遞減斩松。每次找到比基準(zhǔn)數(shù)大的a[i]和比基準(zhǔn)數(shù)小的a[j]后便進(jìn)行交換。一直到i=j觉既，再最后一次交換基準(zhǔn)數(shù)與a[j]惧盹。此時(shí)便實(shí)現(xiàn)了一個(gè)基準(zhǔn)數(shù)左邊比它小，右邊比它大的序列瞪讼。
需要注意的是钧椰，每次必須是j先遞減。原因是這樣最后一次交換時(shí)符欠，保證基準(zhǔn)數(shù)交換的是比它小的a[j]嫡霞。
沒有畫圖來講述整個(gè)過程，還是不懂可以看：坐在馬桶上看算法：快速排序
下面是代碼：
/**
* 快速排序,O(nlogn)
* @param a
* @param left
* @param right
*/
public static void quickSort(int[] a, int left, int right) {
if (left > right)
return;
int middle = a[left]; // 基準(zhǔn)數(shù)
int i = left;
int j = right;
while (i != j) {
// 從最右遞減找出小于基準(zhǔn)數(shù)的數(shù)
while (a[j] >= middle && i < j) {
j--;
}
// 從最左遞增找出大于基準(zhǔn)數(shù)的數(shù)
while (a[i] <= middle && i < j) {
i++;
}
// 交換
swap(a, i, j);
}
// 將基準(zhǔn)數(shù)和最后小于它的數(shù)進(jìn)行交換
a[left] = a[i];
a[i] = middle;
// 以基準(zhǔn)數(shù)劃分左右區(qū)間希柿，再對(duì)左右區(qū)間進(jìn)行快排
quickSort2(a, left, i - 1);
quickSort2(a, i + 1, right);
}
由于a[left]我們已經(jīng)用middle保存了诊沪，所以也可以利用a[left]來作為中間變量交換a[i]和a[j]，優(yōu)化后的代碼如下：
/**
* 快速排序曾撤，O(nlogn)
* @param a
* @param left
* @param right
*/
public static void quickSort(int[] a,int left,int right) {
if(left>right)
return ;
int middle=a[left]; //基準(zhǔn)數(shù)
int i=left;
int j=right;
while (i != j) {
//從最右遞減找出小于基準(zhǔn)數(shù)的數(shù)
while (a[j] >= middle && i < j) {
j--;
}
a[i]=a[j];
//從最左遞增找出大于基準(zhǔn)數(shù)的數(shù)
while (a[i] <= middle && i < j) {
i++;
}
a[j]=a[i];
}
//將基準(zhǔn)數(shù)和最后小于它的數(shù)進(jìn)行交換
a[i]=middle;
//以基準(zhǔn)數(shù)劃分左右區(qū)間端姚，再對(duì)左右區(qū)間進(jìn)行快排
quickSort(a, left, i-1);
quickSort(a, i+1, right);
}
堆排序
堆
堆其實(shí)就是一個(gè)完全二叉樹，分為最大堆（父結(jié)點(diǎn)>=子結(jié)點(diǎn)）挤悉、最小堆（父結(jié)點(diǎn)<=子結(jié)點(diǎn)）渐裸。一般用數(shù)組來存儲(chǔ)，i結(jié)點(diǎn)的父結(jié)點(diǎn)下標(biāo)就為(i – 1) / 2装悲。它的左右子結(jié)點(diǎn)下標(biāo)分別為2i + 1和2i + 2昏鹃。
堆的兩個(gè)操作
要明白堆排序，就要先明白堆的添加和刪除原理衅斩。
- 在堆數(shù)組尾部添加元素時(shí)盆顾，需要不停將該元素與其父結(jié)點(diǎn)進(jìn)行對(duì)比交換，類似于元素在“上升”畏梆。也就是使新添加的元素插入一個(gè)有序的序列中您宪，形成一個(gè)新的有序堆序列
- 堆刪除元素時(shí)，總是先刪除根結(jié)點(diǎn)奠涌，然后將最后一個(gè)元素移到根結(jié)點(diǎn)宪巨，與子結(jié)點(diǎn)對(duì)比交換，類似于元素在“下沉”溜畅。最終形成新的有序堆序列捏卓。
好的，明白堆的添加刪除后慈格，我們就可以解決以下問題：
- 現(xiàn)在給了一個(gè)無(wú)序數(shù)組怠晴，如何將其變成堆數(shù)組遥金？
我們可以對(duì)數(shù)組反向迭代，從末尾開始每個(gè)元素進(jìn)行“下沉處理”蒜田，這樣便保證迭代完成后的數(shù)組是一個(gè)最小堆 - 如何利用堆進(jìn)行排序
由于最小堆的根結(jié)點(diǎn)永遠(yuǎn)是所有元素中最小的稿械。我們可以進(jìn)行刪除操作。依次取出頂點(diǎn)的結(jié)點(diǎn)冲粤，這些取出的頂點(diǎn)最終就形成了一個(gè)遞增序列美莫。
堆排序代碼
注意：下面代碼為了方便，每次取出堆的頂點(diǎn)放入數(shù)組末尾梯捕，最終形成了一個(gè)遞減序列厢呵。也可以將取出的元素新放入另外一個(gè)數(shù)組，形成遞增序列傀顾。
public class Heap {
private int[] a; //堆數(shù)組
private int n; //結(jié)點(diǎn)個(gè)數(shù)
/**
* 構(gòu)造一個(gè)堆化數(shù)組
* @param a 數(shù)組
* @param n 數(shù)組中元素個(gè)數(shù)
*/
public Heap(int[] a,int n) {
this.a = a;
this.n=n;
for (int i = (n-2)/2; i >=0; i--) {
minHeapDown(i,n);
}
}
/**
* 最小堆襟铭，對(duì)index下標(biāo)結(jié)點(diǎn)進(jìn)行“上浮”處理
* @param index
*/
public void minHeapFixUp(int index) {
int temp=a[index];
//index的父結(jié)點(diǎn)
int fIndex=(index-1)/2;
//未到頂點(diǎn)時(shí)繼續(xù)
while(fIndex>=0&&index>0){
//如果該結(jié)點(diǎn)大于父結(jié)點(diǎn)，直接退出循環(huán)
if(a[fIndex]<temp)
break;
//如果該結(jié)點(diǎn)小于父節(jié)點(diǎn)锣笨，則交換結(jié)點(diǎn)
a[index]=a[fIndex];
index=fIndex;
fIndex=(index-1)/2;
}
a[index]=temp;
}
/**
* 最小堆蝌矛，對(duì)index下標(biāo)結(jié)點(diǎn)進(jìn)行“下沉”處理
* @param index
* @param n 堆中元素個(gè)數(shù)
*/
public void minHeapDown(int index,int n) {
int temp=a[index];
int sIndex=2*index+2; //子結(jié)點(diǎn)下標(biāo)為2*index+1、2*index+2
while(sIndex<=n-1){
//找出左右子結(jié)點(diǎn)中最小的一個(gè)
sIndex=(a[sIndex]>a[sIndex-1])?sIndex-1:sIndex;
//如果子結(jié)點(diǎn)比該結(jié)點(diǎn)大错英，退出循環(huán)
if(a[sIndex]>temp)
break;
//如果子節(jié)點(diǎn)比該結(jié)點(diǎn)小，進(jìn)行交換
a[index]=a[sIndex];
index=sIndex;
sIndex=2*index+1;
}
a[index]=temp;
}
/**
* 新添加一個(gè)結(jié)點(diǎn)在堆的下標(biāo)index
* @param index
* @param content
*/
public void add(int index,int content) {
a[index]=content;
minHeapFixUp(index);
}
/**
* 堆的刪除操作隆豹，即刪除頭結(jié)點(diǎn)
*/
public void remove() {
Sort.swap(a, 0, n-1);
minHeapDown(0,n);
}
/**
* 堆排序椭岩，,O(nlogn)
*/
public void minHeapSort(){
for (int i = n-1; i >=1; i--) {
Sort.swap(a, 0, i);
minHeapDown(0,i);
}
}
public static void main(String[] args) {
int[] a={8,9,6,4,7,5,3,4,1};
Heap heap=new Heap(a, a.length);
heap.minHeapSort();
System.out.println(Arrays.toString(a));
}
}/**output:
[9, 8, 7, 6, 5, 4, 4, 3, 1]
*/
幾種排序算法時(shí)間復(fù)雜度的比較
排序算法嚴(yán)格來說沒有最快，各有各的適用環(huán)境璃赡。
如果非要找出一個(gè)最快判哥，筆者通過上網(wǎng)查資料，發(fā)現(xiàn)大多都推薦的是桶排序碉考。
參考
排序（本文圖片出自此網(wǎng)站）
白話經(jīng)典算法系列之七 堆與堆排序
