1、插入排序

• 直接插入排序

時間復(fù)雜度O{n^2}

package 排序.插入排序.直接插入排序;/*** 插入排序 -- 每次從后面選擇一個數(shù)與前面排好序的數(shù)組進行比較，如果小，進行交換并與前面繼續(xù)比較，如果大學(xué)，結(jié)束，并且不交換* 兩層for循環(huán)* 第一層： 確定有序數(shù)組，* 第二層： 使用下一個數(shù)與前面的有序數(shù)組比較，確定合適的位置*/ public class InsertSorted {/*** 這個方法每次比較成功都會執(zhí)行三次賦值，性能略差* @param arr*/public static void sort(int[] arr) {for (int i = 1; i < arr.length; i++) { //從1開始，因為第一個arr[0]已經(jīng)有序for (int j = i; j >=1 && arr[j] < arr[j-1]; j--) { //不斷與前面有序數(shù)組比較，確定合適位置int temp = arr[j]; //執(zhí)行交換arr[j] = arr[j-1];arr[j-1] = temp;}}}//時間復(fù)雜度 O{n^2}/*** 改進的插入排序* @param*/public static void sort2(int[] arr) {for (int i = 1; i < arr.length; i++) {int j; //保存可以插入的位置int temp = arr[i]; //需要插入的元素for (j = i; j >=1 && temp < arr[j-1]; j--) { //不斷與前面有序數(shù)組比較，確定合適位置arr[j] = arr[j-1]; //向后賦值}arr[j] = temp;}}public static void main(String[] args) {int[] arr = {10, 9, 8, 7, 50, 5, 4, 3, 2, 1};InsertSorted.sort2(arr);for(int i = 0; i < arr.length; i ++) {System.out.print(arr[i] + " ");}} }

• 折半插入排序

時間復(fù)雜度O{n^2}(查找次數(shù)減少，移動次數(shù)不變)

package 排序.插入排序.折半插入排序;public class InsertSorted {public static void sort(int[] arr) {for (int i = 1; i < arr.length; i ++) {int temp = arr[i]; //定義臨時變量保存需要插入的值int low = 0, high = i - 1;while (low <= high) {int mid = (low + high) / 2;if (temp < arr[mid]) high = mid - 1; //條件沒有小于，如果有會發(fā)生不穩(wěn)定else low = mid + 1;} //high的后一個位置就是插入的位置//需要插入的位置是high+1,for (int j = i; j > high + 1; j --) {arr[j] = arr[j-1];}arr[high + 1] = temp;}}/*** 時間復(fù)雜度，O(n^2)* 雖然采用了折半插入，但是僅僅在查找過程中時間復(fù)雜度為O(log2n),因為減少了關(guān)鍵字的比較* 但是在數(shù)據(jù)移動時的復(fù)雜度任然為O(n^2),* 但是在性能上還是優(yōu)于直接插入排序* @param args*/public static void main(String[] args) {int[] arr = {10, 9};InsertSorted.sort(arr);for(int i = 0; i < arr.length; i ++) {System.out.print(arr[i] + " ");}} }

• 希爾排序(縮小增量排序)

增量一般為n/2…
時間復(fù)雜度約為O{n^1.3}

package 排序.插入排序.希爾排序;/*** 希爾排序：縮小增量排序，(不穩(wěn)定）* 原理：直接插入排序在 （基本有序，記錄較少） 的情況下有較好的性能*/ public class InsertSorted {public static void sort(int[] arr) {int d = arr.length / 2; //這就是縮小增量的過程while (d > 0) {for (int i = d; i < arr.length; i ++) {int temp = arr[i];int j;for (j = i; j >= d && temp < arr[j - d]; j = j - d) {arr[j] = arr[j - d]; //后移}arr[j] = temp;}d = d / 2 ;}}public static void main(String[] args) {int[] arr = {10, 9, 8, 7, 50, 5, 4, 3, 2, 1};InsertSorted.sort(arr);for(int i = 0; i < arr.length; i ++) {System.out.print(arr[i] + " ");}} }

2、交換排序

• 冒泡排序(幾乎不用)

時間復(fù)雜度O{n^2}

package 排序.交換排序.冒泡排序;public class ExchangeSorted {/*** 時間復(fù)雜度O(n^2),性能較差，交換次數(shù)較多，幾乎不用* @param arr*/public static void sort(int[] arr) {boolean flag = true; //設(shè)置一個監(jiān)視哨，如果在某一趟排序中未發(fā)生交換，說明該序列已經(jīng)有序，可以跳出外層循環(huán)；int m = arr.length;for (int i = 0; i < arr.length && flag; i ++){flag = false;for (int j = 0; j < m - 1; j ++) { //第一趟選擇最大的，第二趟選擇次大的，以此類推。。。。。。if (arr[j] > arr[j + 1]) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;flag = true;}}m--; //因為每一趟都會選出一個最大的值，所以不需要再次向后面進行比較}}public static void main(String[] args) {int[] arr = {10, 9, 8, 7, 50, 5, 4, 3, 2, 1};ExchangeSorted.sort(arr);for(int i = 0; i < arr.length; i ++) {System.out.print(arr[i] + " ");}} }

• 快速排序

時間復(fù)雜度O{nlog2n}（2為底）

package 排序.交換排序.快速排序;/*** 時間復(fù)雜度O(log2n)* 在冒泡排序中，一次交換只能消除一個逆序，而快速排序間隔多個記錄進行交換可能消除多個逆序* 原理：選擇一個pivot（樞軸），經(jīng)過一趟排序后，將小于pivot的放到pivot前面，將大于pivot的放到pivot后面,* 就可以確定該pivot在數(shù)組中的位置（通常選擇第一個記錄為pivot）\\* 適用于初始無序，n較大時* （不穩(wěn)定排序）*/ public class QuickSorted {public static void sort(int[] arr ,int start, int end) {int left = start,right = end;int pivot = arr[left];if (left >= right) return; //遞歸出口的條件，當(dāng)區(qū)間大于零的時候才繼續(xù)執(zhí)行while (left < right) { //一趟排序，結(jié)束條件是當(dāng)left指針和right指針相遇//必須從右邊開始掃描，因為左端的值已經(jīng)放到了臨時變量pivot中，可以進行覆蓋，//如果從左邊開始掃描，就會將右端的值覆蓋，發(fā)生丟失while (left < right && arr[right] >= pivot) right --; //如果右邊的值大于等于pivot，指針左移arr[left] = arr[right];while (left < right && arr[left] <= pivot) left ++; //如果左邊的值小于等于pivot，指針右移arr[right] = arr[left];}arr[left] = pivot; //此時left = right，這個位置就是pivot（arr[start]）應(yīng)該在的位置sort(arr, start, left - 1); //遞歸調(diào)用函數(shù)，這是左區(qū)間sort(arr, left + 1, end); //遞歸調(diào)用函數(shù)，這是右區(qū)間}public static void main(String[] args) {int[] arr = {10, 9, 8, 7, 50, 5, 4, 3, 5, 1};sort(arr,0,arr.length - 1);for(int i = 0; i < arr.length; i ++) {System.out.print(arr[i] + " ");}} }

3、選擇排序

• 簡單選擇排序

時間復(fù)雜度O{n^2}

package 排序.選擇排序.簡單選擇排序;/*** 選擇排序，每次都從未排序中選擇最小的放到最前面，* 利用兩層循環(huán)* 第一層for循環(huán)用于選擇確定需要選擇最小值的數(shù)量* 第二層循環(huán)用于找出剩余數(shù)據(jù)的最小值* 采用尋找最小值下標(biāo)的方法*/ public class SelectedSorted {public static void sort(int[] arr) { //傳入數(shù)組for (int i = 0; i < arr.length; i++) { //第一層循環(huán),每次都設(shè)當(dāng)前循環(huán)位置為最小值位置int minIndex = i;for (int j = i + 1; j < arr.length; j++) { //第二層循環(huán)，遍歷除上一層循環(huán)位置后的所有值，if (arr[j] < arr[minIndex]) { //與最小值位置的值相比較,不斷找到最小值得位置，知道循環(huán)完成minIndex = j;}}int temp = arr[minIndex]; //定義臨時變量，存放最小值arr[minIndex] = arr[i]; //將第一層循環(huán)所在位置的值賦給當(dāng)前最小值所在的位置，完成交換arr[i] = temp; //將最小值賦給第一層循環(huán)所在位置}}/*** 時間復(fù)雜度 為 O{n^2}* @param args*/public static void main(String[] args) {int[] arr = new int[]{10, 9, 8, 7, 50, 5, 4, 3, 2, 1};SelectedSorted.sort(arr);for(int i = 0; i < arr.length; i ++) {System.out.print(arr[i] + " ");}} }

堆排序

時間復(fù)雜度O(nlog2n)，空間復(fù)雜度O(1)  package 排序.選擇排序.堆排序;public class HeapSorted {/*** 篩選法建立堆（大根堆）* @param arr 傳入的數(shù)組* @param start 需要調(diào)整堆的起始位置* @param end 需要調(diào)整堆的結(jié)束位置* 我采用的是數(shù)組下標(biāo)從零開始的數(shù)組，建立* 的堆也是從0開始的，* 所以（cur ！= 2*start）而是（cur = 2 * start + 1）*/public void heapAdjust(int[] arr, int start, int end) { //為數(shù)組的start位置到end位置調(diào)整堆int temp = arr[start]; //使用臨時變量保存arr[start]（就是第一個元素）int cur; //用來指向起始位置(start)的下一個位置for (cur = 2 * start + 1; cur <= end; cur = 2 * start + 1) {//當(dāng)cur指向最后一個元素（cur = end）時，就不需要再判斷arr[cur] < arr[cur + 1]了，因為沒有arr[cur + 1],//如果條件為cur < end && arr[cur] < arr[cur + 1]，會發(fā)生數(shù)組越界if (cur < end && arr[cur] < arr[cur + 1]) cur++;if (temp >= arr[cur]) break; //如果temp（arr[start]>=arr[cur]），跳出循環(huán)，不再往下進行比較arr[start] = arr[cur]; //否則元素上移start = cur; //并且start位置下移}arr[start] = temp;}/*** 建初堆* @param arr （傳入需要建初堆的數(shù)組)** 建立完初堆后，根節(jié)點為最大值*/public void creatHeap(int[] arr) {int n = arr.length;//因為數(shù)組下標(biāo)從0開始，所以（n / 2 - 1）為第一個需要調(diào)整堆的位置，大于（n / 2 - 1)的位置為葉子節(jié)點，符合堆的定義for (int i = n / 2 - 1; i >= 0; --i) { //根節(jié)點也需要調(diào)整堆，所以i >= 0;heapAdjust(arr, i, n - 1); //最后一個元素位置為 n -1 ；}}/*** 堆排序* @param arr (需要堆排序的數(shù)組)*/public void heapSort(int[] arr) {creatHeap(arr); //先建立初堆,現(xiàn)在堆得根結(jié)點為最大值for (int i = arr.length - 1; i > 0; --i) {//將最大值放入最后一個位置,并將最后一個元素放到堆頂，然后繼續(xù)調(diào)整堆，不斷將次大值放入后面相應(yīng)的位置//直到 i == 1,元素有序int temp = arr[0];arr[0] = arr[i];arr[i] = temp;heapAdjust(arr, 0, i - 1); //不斷調(diào)整堆，每次減少最后一個元素位置}}public static void main(String[] args) {int[] arr = new int[] {0,5,9,6,5,8,7,15,2,789,56,145,17,26,0};new HeapSorted().heapSort(arr);for (int temp : arr) {System.out.println(temp);}} }

4、歸并排序

• 二路歸并排序

時間復(fù)雜度O{nlog2n}(n為底)

package 排序.歸并排序.二路歸并排序;public class MSort {/*** 將arr[low~mid]和arr[mid+1~high]合并成一個有序數(shù)組**/public static void merge(int[] arr, int low, int mid, int high) {int i = low, j = mid + 1, k = 0;int[] nArr = new int[high - low +1]; //分配一個新的數(shù)組，用來作為臨時變量,大小為需要歸并的數(shù)組的元素個數(shù)（high-low+1）while (i <= mid && j <= high) { //一個while循環(huán)，不斷選出兩邊最小的數(shù)放到臨時變量中if (arr[i] <= arr[j]) nArr[k++] = arr[i++];else nArr[k++] = arr[j++];}//選出剩下的一端的剩余數(shù)據(jù)放到臨時數(shù)組變量尾部，因為不知道那一邊先結(jié)束，所以設(shè)置了兩個while循環(huán)while (i <= mid) {nArr[k++] = arr[i++];}while (j <= high) {nArr[k++] = arr[j++];}for (int m = low,n = 0; m <= high; m ++, n++) { //使用一個for循環(huán)將臨時變量數(shù)組的值賦給原始數(shù)組，位置為方法參數(shù)傳進的位置arr[m] = nArr[n];}}//進行歸并public static void mergeSort(int[] arr ,int low, int high) {if (low == high) return; //遞歸終止條件int mid = (low + high) / 2;mergeSort(arr,low,mid); //遞歸歸并左部分,（包含mid）mergeSort(arr,mid + 1, high); //遞歸歸并右部分merge(arr,low,mid,high);}public static void main(String[] args) {int[] arr = {5,6,10,7,9,5,6,3,89,54,54,5,2,4,789,566,216,21,4,3446,246};mergeSort(arr,0,arr.length - 1);for (int temp : arr) {System.out.print(temp + " ");}} }

總結(jié)

以上是生活随笔為你收集整理的排序算法（Java实现）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。