柚子快報(bào)激活碼778899分享：算法 Java實(shí)現(xiàn)八種排序

http://yzkb.51969.com/

目錄

分類

直接插入排序

希爾排序

選擇排序

堆排序

冒泡排序

快速排序

挖坑法

?hoare法?

雙指針?lè)?/p>

優(yōu)化

非遞歸實(shí)現(xiàn)?

歸并排序

非遞歸實(shí)現(xiàn)

計(jì)數(shù)排序

分類

這里的排序可以分為兩大類，

基于比較的排序非基于比較的排序

其中有七種基于比較的排序：

直接插入排序希爾排序選擇排序堆排序冒泡排序快速排序歸并排序

一種非基于比較的排序：計(jì)數(shù)排序。

下面會(huì)通過(guò)Java來(lái)實(shí)現(xiàn)這八種排序，快速排序 和 歸并排序 會(huì)有遞歸和非遞歸的實(shí)現(xiàn)。

直接插入排序

思路：

以兩個(gè)for循環(huán)， 來(lái)實(shí)現(xiàn)兩個(gè)數(shù)及兩數(shù)中小數(shù)與前面數(shù)進(jìn)行比較假設(shè)第一個(gè)數(shù)為tmp，認(rèn)為第一個(gè)數(shù)已經(jīng)是排好序的，然后去和后面一個(gè)數(shù)進(jìn)行比較如果 j位置 的數(shù) > j+1位置的數(shù)，把 j位置的數(shù) 賦值給 j+1位置；如果否，則向 j位置的前面去做，直到 j >= 0重復(fù)進(jìn)行步驟3，直到不符合循環(huán)條件

動(dòng)圖如下：

代碼 ：

public static void insertSort(int[] array){

for (int i = 1; i < array.length; i++) {

int tmp = array[i];

int j = i-1;

for (; j >= 0; j--) {

if(array[j] > tmp){

array[j+1] = array[j];

}else{

array[j+1] = tmp;

break;

}

}

array[j+1] = tmp;

}

}

時(shí)間復(fù)雜度：O(N^2)

空間復(fù)雜度：O(1)?

穩(wěn)定性：穩(wěn)定

注意：

本身是一個(gè)穩(wěn)定的排序，那么可以實(shí)現(xiàn)為不穩(wěn)定的?。但是 如果一個(gè)排序 本身就是不穩(wěn)定，那就不能實(shí)現(xiàn)穩(wěn)定的排序。數(shù)據(jù)越有序，直接插入排序越快

希爾排序

步驟：

希爾排序算是對(duì)直接排序進(jìn)行優(yōu)化，把其中的數(shù)據(jù)通過(guò)分組來(lái)不斷簡(jiǎn)化 其中的有序性，上面有提到數(shù)據(jù)越有序，直接插入排序越快，不過(guò)這個(gè)分組并不是常規(guī)理解的那種把幾個(gè)臨近的數(shù)字化為一個(gè)組，而是，如下圖所示：

通過(guò)間隔（gap）來(lái)實(shí)現(xiàn)分組，以上面 紫色的原圖 為例，這時(shí)的gap為5，這代表著隔著5個(gè)空格的數(shù)為一組，然后進(jìn)行組內(nèi)排序，不斷縮小間隔，增加每組內(nèi)元素個(gè)數(shù)，再次進(jìn)一步比較。

動(dòng)圖如下：

代碼：

通過(guò)代碼部分，我們也能看出這里面有直接排序的存在，只不過(guò)其中的部分和希爾排序有些出入。

public static void shellInsert(int[] array){

int gap = array.length;

while(gap > 1){

gap /= 2;

shell(array, gap);

}

}

private static void shell(int[] array, int gap) {

for (int i = gap; i < array.length; i++) {

int tmp = array[i];

int j = i-gap;

for (; j >= 0; j-= gap) {

if(array[j] > tmp){

array[j+gap] = array[j];

}else{

array[j+gap] = tmp;

break;

}

}

array[j+gap] = tmp;

}

}

?時(shí)間復(fù)雜度：O(N^1.2) - O(N^1.3)

空間復(fù)雜度：O(1)

穩(wěn)定性：不穩(wěn)定

選擇排序

第一種思路

步驟：

選擇排序，從名字上我們可以理解為從中不斷選擇出最小值，然后把它交換、排到前面之所以說(shuō)是不斷選出最小值，是因?yàn)槊看芜x出最小值都是以 i位置為準(zhǔn)，而i位置也會(huì)不斷變化，兩個(gè)for循環(huán)來(lái)實(shí)現(xiàn)

動(dòng)圖如下：?

代碼：

public static void selectSort(int[] array){

for (int i = 0; i < array.length; i++) {

int minIndex = i;

for (int j = i+1; j < array.length; j++) {

if(array[j] < array[minIndex]){

minIndex = j;

}

}

swap(array,i,minIndex);

}

}

private static void swap(int[] array, int i, int minIndex) {

int tmp = array[i];

array[i] = array[minIndex];

array[minIndex] = tmp;

}

因?yàn)槠渲杏性匚恢玫慕粨Q，所以我們可以自己寫一個(gè)元素位置交換的方法。?

時(shí)間復(fù)雜度：O(N^2)?? 和數(shù)據(jù) 是否有序無(wú)關(guān)

空間復(fù)雜度：O(1)

穩(wěn)定性：不穩(wěn)定

第二種思路

步驟：

這里主要是通過(guò)雙指針的方法來(lái)找到 最小值 和 最大值的位置，當(dāng)然，這是相對(duì)于每次i位置的數(shù)的大小。整體過(guò)程和上面一種思路有些相似的部分，相對(duì)來(lái)說(shuō)，掌握兩種方法還是要好一點(diǎn)。

public static void selectSort1(int[] array){

int left = 0;

int right = array.length-1;

while(left < right){

int minIndex = left;

int maxIndex = left;

for (int i = left+1; i <= right; i++) {

if(array[i] < array[minIndex]){

minIndex = i;

}

if(array[i] > array[maxIndex]){

maxIndex = i;

}

}

swap(array, left, minIndex);

//確保最大值的位置，最大值正好是 left 下標(biāo)

//此時(shí)把最大值換到了minIndex下標(biāo)

if(maxIndex == 0){

maxIndex = minIndex;

}

swap(array, right, maxIndex);

left++;

right--;

}

}

private static void swap(int[] array, int i, int minIndex) {

int tmp = array[i];

array[i] = array[minIndex];

array[minIndex] = tmp;

}

堆排序

步驟：

通過(guò)向下調(diào)整，創(chuàng)建一棵大根堆的樹(shù)通過(guò)把根節(jié)點(diǎn)和最后一個(gè)分支節(jié)點(diǎn)進(jìn)行交換再進(jìn)行向下調(diào)整，完成排序

這個(gè)思路主要是通過(guò)大根堆的由大到小的原理，再通過(guò)換位來(lái)實(shí)現(xiàn)排序。

代碼：

public static void heapSort(int[] array){

createHeap(array);

int end = array.length-1;

while(end > 0){

swap(array, 0 ,end);

siftDown(array, 0,end);

end--;

}

}

//創(chuàng)建大根堆

public static void createHeap(int[] array){

//length-1為最后一棵子樹(shù)，-1 / 2 是為了找到最后一棵子樹(shù)的根節(jié)點(diǎn)

for (int parent = (array.length-1-1)/2; parent >= 0; parent--) {

siftDown(array,parent,array.length);//向下調(diào)整，創(chuàng)建大根堆

}

}

/**

*

* @param array

* @param parent 每棵子樹(shù)調(diào)整的根節(jié)點(diǎn)

* @param length 每棵子樹(shù)調(diào)整的結(jié)束節(jié)點(diǎn)，跳到最后

*/

public static void siftDown(int[] array, int parent, int length) {

int child = 2*parent+1;

while(child < length){

if(child + 1 < length && array[child] < array[child +1]){

child++;

}

if(array[child] > array[parent]){

swap(array, child, parent);

parent = child;

child = 2*parent+1;

}else{

break;

}

}

}

private static void swap(int[] array, int i, int minIndex) {

int tmp = array[i];

array[i] = array[minIndex];

array[minIndex] = tmp;

}

時(shí)間復(fù)雜度：O(N*logN) 空間復(fù)雜度：O(1)

穩(wěn)定性：不穩(wěn)定

冒泡排序

步驟：

通過(guò)相鄰的兩個(gè)元素相互比較，若 前位置 比 后位置的數(shù)要大，進(jìn)行交換

動(dòng)圖如下：

下面代碼部分是優(yōu)化后的部分，未優(yōu)化則不包含(flg元素 和 -i操作 )

代碼：

public static void bubbleSort(int[] array){

for (int i = 0; i < array.length-1; i++) {

boolean flg = false;

for (int j = 0; j < array.length-1-i; j++) {

if(array[j] > array[j+1]){

swap(array, j, j+1);

flg = true;

}

}

//優(yōu)化后的情況

//n個(gè)數(shù)據(jù)，比較n-1次，有可能其中i次就有序了

if(!flg){

break;

}

}

}

private static void swap(int[] array, int i, int minIndex) {

int tmp = array[i];

array[i] = array[minIndex];

array[minIndex] = tmp;

}

時(shí)間復(fù)雜度：不優(yōu)化的情況（沒(méi)有下方的boolean元素和-i操作） O(n^2)

? ? ? ? ? ? ? ? ? ? ?優(yōu)化以后，最快情況能達(dá)到O(N)

空間復(fù)雜度：O(1)?

穩(wěn)定性：穩(wěn)定

快速排序

快速排序有三種方式能來(lái)實(shí)現(xiàn)

挖坑法hoare法雙指針?lè)?/p>

如果問(wèn)題問(wèn)到快速排序，優(yōu)先使用挖坑法，其次hoare法、雙指針?lè)?/p>

挖坑法

步驟：

先是實(shí)現(xiàn) 保證一個(gè)數(shù)的左邊都比它小，右邊都比它大，具體步驟如下步驟2，3，4把第一個(gè)數(shù)存起來(lái)，為tmp，第一個(gè)位置當(dāng)作是坑從后面找比tmp小的值，放到坑里面，后面被放入坑的數(shù)的位置再當(dāng)作坑從前面找比tmp大的值，放到坑里面，前面被放入坑的數(shù)的位置當(dāng)作坑再向兩邊進(jìn)行遞歸來(lái)處理

動(dòng)圖如下：

代碼：

public static void quickSort(int[] array){

quick(array,0,array.length-1);

}

private static void quick(int[] array, int start, int end){

// = 是為了應(yīng)對(duì)沒(méi)有右邊的情況，遞歸結(jié)束條件

if(start >= end){

return;

}

//整個(gè)方法走完之后，為第一次交換位置

int pivot = partition1(array, start, end);

quick(array, start, pivot-1);

quick(array, pivot+1, end);

}

private static int partition1(int[] array, int left, int right) {

int tmp = array[left];

while(left < right){

//循環(huán)找，不循環(huán)時(shí)則代表找到，找到比tmp小的數(shù)

while(left < right && array[right] >= tmp){

right--;

}

//挖坑法，然后填坑

//先是把第一個(gè)位置當(dāng)作空，從后面數(shù)，如果有數(shù)比它小，就放到第一位

//然后是從前數(shù)，找最大值，找到后放到，剛剛的位置

//最后再把第一個(gè)數(shù)放到right和left相交的位置

//方法就是把兩邊的數(shù)分大小放到第一個(gè)數(shù)兩邊

array[left] = array[right];

//找到比tmp大的數(shù)

while(left < right && array[left] <= tmp){

left++;

}

array[right] = array[left];

}

array[left] = tmp;

return left;

}

?hoare法?

步驟：

先是實(shí)現(xiàn) 保證一個(gè)數(shù)的左邊都比它小，右邊都比它大，具體步驟如下步驟2，3，4把第一個(gè)數(shù)存起來(lái)，為tmptmp和后面的數(shù)進(jìn)行比較，然后把小數(shù)放到tmp前面，大數(shù)放到tmp后面遞歸實(shí)現(xiàn)對(duì)tmp兩邊進(jìn)行排序

代碼如下：

public static void quickSort(int[] array){

quick(array,0,array.length-1);

}

private static void quick(int[] array, int start, int end){

// = 是為了應(yīng)對(duì)沒(méi)有右邊的情況，遞歸結(jié)束條件

if(start >= end){

return;

}

//整個(gè)方法走完之后，為第一次交換位置

int pivot = partition(array, start, end);

quick(array, start, pivot-1);

quick(array, pivot+1, end);

}

private static int partition(int[] array, int left, int right) {

int tmp = array[left];

int tmpleft = left;

while(left < right){

//循環(huán)找，不循環(huán)時(shí)則代表找到

//right是為了把右邊的小數(shù)移到左邊

while(left < right && array[right] >= tmp){

right--;

}

while(left < right && array[left] <= tmp){

left++;

}

swap(array, left, right);

}

//因?yàn)閘eft所找的是把左邊的大數(shù)放到右邊，所以找到最后的數(shù)會(huì)比left小，進(jìn)行交換

swap(array,left,tmpleft);

return left;

}

private static void swap(int[] array, int i, int minIndex) {

int tmp = array[i];

array[i] = array[minIndex];

array[minIndex] = tmp;

}

雙指針?lè)?/p>

步驟：

這個(gè)主要是靠 cur + left 雙指針來(lái)實(shí)現(xiàn)排序的，通過(guò)前后條件判斷來(lái)進(jìn)行排序

代碼如下：

public static void quickSort(int[] array){

quick(array,0,array.length-1);

}

private static void quick(int[] array, int start, int end){

// = 是為了應(yīng)對(duì)沒(méi)有右邊的情況，遞歸結(jié)束條件

if(start >= end){

return;

}

//整個(gè)方法走完之后，為第一次交換位置

int pivot = partition3(array, start, end);

quick(array, start, pivot-1);

quick(array, pivot+1, end);

}

public static int partition3(int[] array, int left, int right){

int prev = left;

int cur = left+1;

while(cur <= right){

if(array[left] > array[cur] && array[cur] != array[prev]){

swap(array, cur, prev);

}

cur++;

}

swap(array,prev,left);

return prev;

}

private static void swap(int[] array, int i, int minIndex) {

int tmp = array[i];

array[i] = array[minIndex];

array[minIndex] = tmp;

}

關(guān)于快速排序

時(shí)間復(fù)雜度：當(dāng)數(shù)據(jù)給定的是1 2 3 4 5 6……有序的情況是 O(n^2)?

? ? ? ? ? ? ? ? ? ? ? 最好的情況是O(N*logN)均勻分為叉，滿二叉樹(shù)

空間復(fù)雜度：最壞情況，遞歸是要開(kāi)辟內(nèi)存的O(N),最好的情況，滿二叉樹(shù)O(logN)

穩(wěn)定性：不穩(wěn)定

優(yōu)化

通過(guò)上面三種方法，我們能看到三種方法中都有遞歸方式，每次遞歸都需要開(kāi)辟內(nèi)存，那么我們可以采取怎樣的方式來(lái)減少遞歸的次數(shù)？

通過(guò)下面兩種方法可以實(shí)現(xiàn)我們的想法：

三數(shù)取中 直接插入法【針對(duì)一定范圍】

關(guān)于三數(shù)取中的意思是：找到左、右、中三個(gè)數(shù)的中位數(shù)。

?部分直接插入，也可以減少遞歸次數(shù)，因?yàn)閿?shù)據(jù)有越有序，直接插入法越快。

代碼部分如下：

public class Sort {

public static void quickSort(int[] array){

quick(array,0,array.length-1);

}

private static void quick(int[] array, int start, int end){

// = 是為了應(yīng)對(duì)沒(méi)有右邊的情況，遞歸結(jié)束條件

if(start >= end){

return;

}

if(end - start + 1 <= 7){

insertSortRange(array, start, end);

return;

}

int minIndex = getMiddleNum(array, start, end);

swap(array, start, minIndex);

//整個(gè)方法走完之后，為第一次交換位置

int pivot = partition1(array, start, end);

quick(array, start, pivot-1);

quick(array, pivot+1, end);

}

public static void insertSortRange(int[] array, int start, int end){

for (int i = start+1; i <= end; i++) {

int tmp = array[i];

int j = i-1;

for (; j >= start; j--) {

if(array[j] > tmp){

array[j+1] = array[j];

}else{

array[j+1] = tmp;

break;

}

}

array[j+1] = tmp;

}

}

private static int getMiddleNum(int[] array, int left, int right){

int mid = (left+right)/2;

if(array[left] < array[right]){

if(array[mid] < array[left]){

return left;

}else if(array[mid] > array[right]){

return right;

}else{

return mid;

}

}else{

if(array[mid] > array[left]){

return left;

}else if(array[mid] < array[right]){

return right;

}else{

return mid;

}

}

}

private static int partition1(int[] array, int left, int right) {

int tmp = array[left];

while(left < right){

//循環(huán)找，不循環(huán)時(shí)則代表找到，找到比tmp小的數(shù)

while(left < right && array[right] >= tmp){

right--;

}

//挖坑法，然后填坑

//先是把第一個(gè)位置當(dāng)作空，從后面數(shù)，如果有數(shù)比它小，就放到第一位

//然后是從前數(shù)，找最大值，找到后放到，剛剛的位置

//最后再把第一個(gè)數(shù)放到right和left相交的位置

//方法就是把兩邊的數(shù)分大小放到第一個(gè)數(shù)兩邊

array[left] = array[right];

//找到比tmp大的數(shù)

while(left < right && array[left] <= tmp){

left++;

}

array[right] = array[left];

}

array[left] = tmp;

return left;

}

private static void swap(int[] array, int left, int right){

int tmp = array[left];

array[left] = array[right];

array[right] = tmp;

}

}

非遞歸實(shí)現(xiàn)?

非遞歸實(shí)現(xiàn)，主要是棧的使用，通過(guò)控制出棧和入棧的元素及其順序來(lái)實(shí)現(xiàn)

代碼如下：

public static void quickSort(int[] array){

quickNor(array,0,array.length-1);

}

private static void quickNor(int[] array, int start, int end){

Deque stack = new ArrayDeque<>();

int pivot = partition1(array, start, end);

//pivot左邊有兩個(gè)元素

if(pivot > start+1){

stack.push(start);

stack.push(pivot-1);

}

if(pivot < end-1){

stack.push(pivot+1);

stack.push(end);

}

while(!stack.isEmpty()){

end = stack.pop();

start = stack.pop();

pivot = partition1(array, start, end);

if(pivot > start+1){

stack.push(start);

stack.push(pivot-1);

}

if(pivot < end-1){

stack.push(pivot+1);

stack.push(end);

}

}

}

private static int partition1(int[] array, int left, int right) {

int tmp = array[left];

while(left < right){

//循環(huán)找，不循環(huán)時(shí)則代表找到，找到比tmp小的數(shù)

while(left < right && array[right] >= tmp){

right--;

}

//挖坑法，然后填坑

//先是把第一個(gè)位置當(dāng)作空，從后面數(shù)，如果有數(shù)比它小，就放到第一位

//然后是從前數(shù)，找最大值，找到后放到，剛剛的位置

//最后再把第一個(gè)數(shù)放到right和left相交的位置

//方法就是把兩邊的數(shù)分大小放到第一個(gè)數(shù)兩邊

array[left] = array[right];

//找到比tmp大的數(shù)

while(left < right && array[left] <= tmp){

left++;

}

array[right] = array[left];

}

array[left] = tmp;

return left;

}

private static void swap(int[] array, int left, int right){

int tmp = array[left];

array[left] = array[right];

array[right] = tmp;

}

歸并排序

步驟：

先把要排序的元素分為兩個(gè)組，接著繼續(xù)向下分組(有種遞歸的味道了)把每組元素比較完后，再把兩個(gè)有序數(shù)組組合起來(lái)

代碼如下：?

public static void mergeSort(int[] array){

mergeSortTmp(array, 0, array.length-1);

}

//遞歸實(shí)現(xiàn)歸并排序

private static void mergeSortTmp(int[] array, int left, int right) {

if(left >= right){

return;

}

//找中間值

int mid = (left + right)/2;

mergeSortTmp(array, left, mid-1);

mergeSortTmp(array, mid+1, right);

//走到這里，相當(dāng)于全部分解完

//合并，合并有序數(shù)組

merge(array, left, mid, right);

}

private static void merge(int[] array, int left, int mid, int right) {

int[] tmp = new int[right-left+1];

int k = 0;

int s1 = left;

int e1 = mid;

int s2 = mid+1;

int e2 = right;

while(s1 <= e1 && s2 <= e2){

if(array[s1] <= array[s2]){

tmp[k++] = array[s1++];

}else {

tmp[k++] = array[s2++];

}

}

while(s1 <= e1){

tmp[k++] = array[s1++];

}

while(s2 <= e2){

tmp[k++] = array[s2++];

}

//可以保證tmp數(shù)組是有序的

for (int i = 0; i < k; i++) {

array[i+left] = tmp[i];

}

}

時(shí)間復(fù)雜度：O(N*logN)

空間復(fù)雜度：O(N)

穩(wěn)定性：穩(wěn)定

非遞歸實(shí)現(xiàn)

非遞歸的實(shí)現(xiàn)，主要依靠的間隔gap的不斷變大，然后通過(guò)每一小部分的排序進(jìn)而來(lái)實(shí)現(xiàn)整個(gè)數(shù)據(jù)組的排序

代碼如下：

?

public static void mergeSortNor(int[] array){

int gap =1;

while(gap < array.length){

for (int i = 0; i < array.length; i = i + gap*2) {

int left = i;

int mid = (left + gap -1);

if(mid >= array.length){

mid = array.length-1;

}

int right = mid + gap;

if(right >= array.length){

right = array.length-1;

}

merge(array, left, mid, right);

}

gap *= 2;

}

}

private static void merge(int[] array, int left, int mid, int right) {

int[] tmp = new int[right-left+1];

int k = 0;

int s1 = left;

int e1 = mid;

int s2 = mid+1;

int e2 = right;

while(s1 <= e1 && s2 <= e2){

if(array[s1] <= array[s2]){

tmp[k++] = array[s1++];

}else {

tmp[k++] = array[s2++];

}

}

while(s1 <= e1){

tmp[k++] = array[s1++];

}

while(s2 <= e2){

tmp[k++] = array[s2++];

}

//可以保證tmp數(shù)組是有序的

for (int i = 0; i < k; i++) {

array[i+left] = tmp[i];

}

}

計(jì)數(shù)排序

非基于比較的排序

還有桶排序， 基數(shù)排序，感興趣可以了解一下

使用場(chǎng)景：集中在某個(gè)范圍內(nèi)的一組數(shù)據(jù)

?步驟：

根據(jù)數(shù)據(jù)的個(gè)數(shù)來(lái)創(chuàng)建數(shù)組把對(duì)應(yīng)元素出現(xiàn)的個(gè)數(shù)給到對(duì)應(yīng)的位置，記錄出現(xiàn)的次數(shù)根據(jù)記錄的次數(shù)，依次輸出元素

代碼如下 ：

public static void countSort(int[] array){

//1.找最大值 和 最小值 來(lái)確定 計(jì)數(shù)數(shù)組的大小

int maxVal = array[0];

int minVal = array[0];

for (int i = 1; i < array.length; i++) {

if(array[i] > maxVal){

maxVal = array[i];

}

if(array[i] < minVal){

minVal = array[i];

}

}

int len = maxVal - minVal + 1;

int[] count = new int[len];

//2.遍歷原來(lái)的數(shù)組array， 把每個(gè)元素 放到對(duì)應(yīng)的計(jì)數(shù)數(shù)組中 進(jìn)行比較

for (int i = 0; i < array.length; i++) {

int index = array[i];

count[index-minVal]++;

}

//3.依次 遍歷計(jì)數(shù)數(shù)組

int index = 0;

for (int i = 0; i < count.length; i++) {

while(count[i] != 0){

array[index] = i+minVal;

index++;

count[i]--;

}

}

}

柚子快報(bào)激活碼778899分享：算法 Java實(shí)現(xiàn)八種排序

http://yzkb.51969.com/

推薦閱讀