概念

概念解釋穩(wěn)定如果a原本在b前面，而a=b，排序之后a仍然在b的前面。不穩(wěn)定如果a原本在b的前面，而a=b，排序之后 a 可能會(huì)出現(xiàn)在 b 的后面。時(shí)間復(fù)雜度對(duì)排序數(shù)據(jù)的總的操作次數(shù)，反映當(dāng)n變化時(shí)，操作次數(shù)所呈現(xiàn)規(guī)律。空間復(fù)雜度算法在計(jì)算機(jī)內(nèi)執(zhí)行時(shí)所需存儲(chǔ)空間，反映當(dāng)n變化時(shí)，存儲(chǔ)空間所呈現(xiàn)規(guī)律。

1、冒泡排序/簡(jiǎn)單比較排序

冒泡排序是簡(jiǎn)單比較排序。 冒泡排序?qū)?shù)組的無(wú)序部分進(jìn)行循環(huán)比較，每次比較兩個(gè)元素，如果順序錯(cuò)誤就進(jìn)行位置交換，循環(huán)結(jié)束后會(huì)在無(wú)序部分的尾部得到最值，成為有序部分；然后繼續(xù)對(duì)剩余的無(wú)序部分進(jìn)行循環(huán)比較，直到整個(gè)數(shù)組都成為有序部分為止。

助記碼：

i∈[0,N-1) //循環(huán)N-1遍j∈[0,N-1-i) //每遍循環(huán)要處理的無(wú)序部分swap(j,j+1) //相鄰元素排序并交換位置

復(fù)雜度和穩(wěn)定性：

復(fù)雜度解釋時(shí)間復(fù)雜度外循環(huán)和內(nèi)循環(huán)以及判斷和交換元素的時(shí)間開(kāi)銷(xiāo) (n-1) + (n-2) + (n-3) + … + 1 = n*(n-1)/2空間復(fù)雜度在交換元素時(shí)那個(gè)臨時(shí)變量所占的內(nèi)存空間平均時(shí)間復(fù)雜度最差時(shí)間復(fù)雜度無(wú)順序標(biāo)志位最優(yōu)時(shí)間復(fù)雜度有順序標(biāo)志位最優(yōu)時(shí)間復(fù)雜度雜序 O( n^2 )逆序 O( n^2 )順序無(wú)標(biāo)志位 O( n^2 )順序有標(biāo)志位 O(n)平均空間復(fù)雜度最差空間復(fù)雜度最優(yōu)空間復(fù)雜度雜序 O(1)逆序 O(1)順序且不使用臨時(shí)空間來(lái)交換兩個(gè)元素O(0)穩(wěn)定性穩(wěn)定不使用臨時(shí)空間來(lái)交換兩個(gè)元素a = a + b; b = a - b; a = a - b;a = a * b; b = a / b; a = a / b;a = a ^ b; b = a ^ b; a = a ^ b;

Java代碼實(shí)現(xiàn)：

public class BubbleSort {public static void main(String[] args) {//TODO 冒泡排序int[] arr = new int[]{10, 9, 8, 7, 6, 5, 4, 3, 2, 1};int[] result = sort(arr);System.out.println("結(jié)果");for (int value : result) {System.out.print(value + " ");}}/*** @param arr 待排序的數(shù)組* @return*/private static int[] sort(int[] arr) {//數(shù)組大小int n = arr.length;//臨時(shí)值放在循環(huán)外，提高效率int temp;for (int i = 0; i < n - 1; i++) {//外層循環(huán)，n個(gè)數(shù)比較，只需要循環(huán)比較n-1次。for (int j = 0; j < arr.length - 1 - i; j++) {//內(nèi)層無(wú)序部分循環(huán)，循環(huán)結(jié)束后，將取出最值置于數(shù)組后端有序部分。if (arr[j] > arr[j + 1]) {//相鄰元素比較替換，前者大于后者替換為升序，前者小于后者替換為降序。temp = arr[j + 1];arr[j + 1] = arr[j];arr[j] = temp;}}System.out.println("第" + (i + 1) + "次");for (int value : arr) {System.out.print(value + " ");}System.out.println(" ");}return arr;} }

運(yùn)行結(jié)果：

第1次 9 8 7 6 5 4 3 2 1 10 第2次 8 7 6 5 4 3 2 1 9 10 第3次 7 6 5 4 3 2 1 8 9 10 第4次 6 5 4 3 2 1 7 8 9 10 第5次 5 4 3 2 1 6 7 8 9 10 第6次 4 3 2 1 5 6 7 8 9 10 第7次 3 2 1 4 5 6 7 8 9 10 第8次 2 1 3 4 5 6 7 8 9 10 第9次 1 2 3 4 5 6 7 8 9 10 結(jié)果 1 2 3 4 5 6 7 8 9 10

有判斷是否順序的標(biāo)志位的冒泡排序，Java代碼實(shí)現(xiàn)：

public class BubbleSort {public static void main(String[] args) {//TODO 冒泡排序int[] arr = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};int[] result = sort(arr);System.out.println("結(jié)果");for (int value : result) {System.out.print(value + " ");}}/*** @param arr 待排序的數(shù)組* @return*/private static int[] sort(int[] arr) {//數(shù)組大小int n = arr.length;//臨時(shí)值放在循環(huán)外，提高效率int temp;//是否順序的標(biāo)志位int flag = 1;for (int i = 0; i < n - 1; i++) {//外層循環(huán)，n個(gè)數(shù)比較，只需要循環(huán)比較n-1次。for (int j = 0; j < arr.length - 1 - i; j++) {//內(nèi)層無(wú)序部分循環(huán)，循環(huán)結(jié)束后，將取出最值置于數(shù)組后端有序部分。if (arr[j] > arr[j + 1]) {//相鄰元素比較替換，前者大于后者替換為升序，前者小于后者替換為降序。temp = arr[j + 1];arr[j + 1] = arr[j];arr[j] = temp;flag = 0;}}System.out.println("第" + (i + 1) + "次");for (int value : arr) {System.out.print(value + " ");}System.out.println(" ");//是順序if (flag==1) break;}return arr;} }

運(yùn)行結(jié)果：

第1次 1 2 3 4 5 6 7 8 9 10 結(jié)果 1 2 3 4 5 6 7 8 9 10

2、簡(jiǎn)單選擇排序

簡(jiǎn)單選擇排序，將數(shù)組的無(wú)序部分中的元素進(jìn)行比較，得到最值，并與無(wú)序部分的首部交換位置，成為數(shù)組的有序部分；然后繼續(xù)對(duì)剩余的無(wú)序部分執(zhí)行相同操作，直到整個(gè)數(shù)組都成為有序部分為止。

助記碼：

i∈[0,N-1) //循環(huán)N-1遍j∈[i+1,N) //每遍循環(huán)要處理的無(wú)序部分select(min) //選擇最值swap(i, min) //交換最值和無(wú)序部分的首部位置

復(fù)雜度和穩(wěn)定性：

平均時(shí)間復(fù)雜度最差時(shí)間復(fù)雜度最優(yōu)時(shí)間復(fù)雜度空間復(fù)雜度穩(wěn)定性O(shè)( n^2 )O( n^2 )O( n^2 )O(1)不穩(wěn)定

Java代碼實(shí)現(xiàn)：

public class SelectionSort {public static void main(String[] args) {//TODO 選擇排序int[] arr = new int[]{10, 2, 8, 3, 6, 8, 4, 7, 9, 1};int[] result = sort(arr);System.out.println("結(jié)果");for (int value : result) {System.out.print(value + " ");}}/*** @param arr 待排序的數(shù)組* @return*/private static int[] sort(int[] arr) {//臨時(shí)值放在循環(huán)外，提高效率int miniIndex, miniValue;for (int i = 0; i < arr.length - 1; i++) {//外層循環(huán)，n個(gè)數(shù)比較，只需要循環(huán)比較n-1次。miniIndex = i;for (int j = i + 1; j < arr.length; j++) {//內(nèi)層循環(huán)，對(duì)無(wú)序部分進(jìn)行比較，得到最值if (arr[miniIndex] > arr[j]) {miniIndex = j;}}//得到最值后，將最值與無(wú)序部分的首部進(jìn)行位置互換，成為數(shù)組的有序部分miniValue = arr[miniIndex];arr[miniIndex] = arr[i];arr[i] = miniValue;System.out.println("第" + (i + 1) + "次");for (int value : arr) {System.out.print(value + " ");}System.out.println(" ");}return arr;} }

運(yùn)行結(jié)果：

第1次 1 2 8 3 6 8 4 7 9 10 第2次 1 2 8 3 6 8 4 7 9 10 第3次 1 2 3 8 6 8 4 7 9 10 第4次 1 2 3 4 6 8 8 7 9 10 第5次 1 2 3 4 6 8 8 7 9 10 第6次 1 2 3 4 6 7 8 8 9 10 第7次 1 2 3 4 6 7 8 8 9 10 第8次 1 2 3 4 6 7 8 8 9 10 第9次 1 2 3 4 6 7 8 8 9 10 結(jié)果 1 2 3 4 6 7 8 8 9 10

3、簡(jiǎn)單插入排序

取出未排序無(wú)序序列中的首部元素，在數(shù)組首部已排序有序序列中從后向前掃描，找到相應(yīng)位置并插入，也就是未找到相應(yīng)位置時(shí)進(jìn)行位置交換，找到相應(yīng)位置時(shí)停止位置交換，成為有序序列；然后繼續(xù)從剩余無(wú)序序列中取出首部元素，進(jìn)行插入，直到整個(gè)數(shù)組成為有序序列。例如撲克牌排序。

簡(jiǎn)單插入排序在小規(guī)模數(shù)據(jù)數(shù)據(jù)或者基本有序或者時(shí)十分高效。數(shù)據(jù)有序程度越高，越高效，移動(dòng)少。

復(fù)雜度和穩(wěn)定性：

平均時(shí)間復(fù)雜度最差時(shí)間復(fù)雜度最優(yōu)時(shí)間復(fù)雜度空間復(fù)雜度穩(wěn)定性O(shè)( n^2 )O( n^2 )O( n )O(1)穩(wěn)定

Java實(shí)現(xiàn)代碼：

public class InsertionSort {public static void main(String[] args) {//TODO 插入排序int[] arr = new int[]{10, 2, 8, 3, 6, 5, 4, 7, 9, 1};int[] result = sort(arr);System.out.println("結(jié)果");for (int value : result) {System.out.print(value + " ");}}/*** @param arr 待排序的數(shù)組* @return*/private static int[] sort(int[] arr) {if (arr == null || arr.length < 2) {return arr;}int len = arr.length;int preIndex, current;//可以把數(shù)組首部元素，當(dāng)做已排序的有序序列for (int i = 1; i < len; i++) {//已排序序列的最后一個(gè)元素preIndex = i - 1;//未排序序列的第一個(gè)元素current = arr[i];//尋找當(dāng)前元素在有序序列中的相應(yīng)位置，未結(jié)束循環(huán)且有序序列前一個(gè)元素比當(dāng)前元素大，則繼續(xù)尋找while (preIndex >= 0 && arr[preIndex] > current) {//交換位置arr[preIndex + 1] = arr[preIndex];//繼續(xù)尋找preIndex--;}//如果已排序序列已經(jīng)循環(huán)完畢，或者，已經(jīng)找到對(duì)應(yīng)位置arr[preIndex + 1] = current;System.out.println("第" + i + "次");for (int value : arr) {System.out.print(value + " ");}System.out.println(" ");}return arr;} }

運(yùn)行結(jié)果：

第1次 2 10 8 3 6 5 4 7 9 1 第2次 2 8 10 3 6 5 4 7 9 1 第3次 2 3 8 10 6 5 4 7 9 1 第4次 2 3 6 8 10 5 4 7 9 1 第5次 2 3 5 6 8 10 4 7 9 1 第6次 2 3 4 5 6 8 10 7 9 1 第7次 2 3 4 5 6 7 8 10 9 1 第8次 2 3 4 5 6 7 8 9 10 1 第9次 1 2 3 4 5 6 7 8 9 10 結(jié)果 1 2 3 4 5 6 7 8 9 10

4、希爾排序/改進(jìn)版簡(jiǎn)單插入排序/縮小增量排序/遞減增量排序

希爾排序改進(jìn)插入排序，使得對(duì)較大規(guī)模并且無(wú)序的數(shù)據(jù)也非常有效率

與簡(jiǎn)單插入排序的不同之處在于，希爾排序會(huì)優(yōu)先比較距離較遠(yuǎn)的元素。

首先它在邏輯上把較大的數(shù)據(jù)集合分割成若干個(gè)小組，然后對(duì)每一個(gè)小組分別進(jìn)行插入排序，此時(shí)，插入排序所作用的每一個(gè)小組的數(shù)據(jù)量比較小，插入的效率比較高。

當(dāng)增量為1時(shí)，整個(gè)數(shù)組已經(jīng)接近有序了，插入排序效率高。

希爾排序的核心在于間隔序列的設(shè)定。既可以提前設(shè)定好間隔序列，也可以動(dòng)態(tài)的定義間隔序列。

希爾排序的時(shí)間度分析極其復(fù)雜，有的增量序列的復(fù)雜度至今還沒(méi)人能夠證明出來(lái)。

Hibbard提出了另一個(gè)增量序列{1,3,7，...,2^k-1 }，這種序列的時(shí)間復(fù)雜度(最壞情形)為O(n^1.5 )

Sedgewick提出了幾種增量序列，其最壞情形運(yùn)行時(shí)間為O（n^1.3 ）,其中最好的一個(gè)序列是{1,5,19,41,109,...}

雖然插入排序是穩(wěn)定的，但是希爾排序在插入的時(shí)候是跳躍性插入的，有可能破壞穩(wěn)定性。

復(fù)雜度和穩(wěn)定性：

空間復(fù)雜度穩(wěn)定性O(shè)(1)不穩(wěn)定

Java代碼實(shí)現(xiàn)：

public class ShellSort {public static void main(String[] args) {//TODO 希爾排序int[] arr = new int[]{10, 2, 8, 3, 6, 8, 4, 7, 9, 1};int[] result = sort(arr);System.out.println("結(jié)果");for (int value : result) {System.out.print(value + " ");}}private static int[] sort(int[] arr) {int length = arr.length;int current;int incrementTime=0;for (int increment = length / 2; increment >= 1; increment /= 2) {incrementTime++;System.out.println("第" + incrementTime + "組" + increment +"增量");int insertTime = 0;for (int i = increment; i < length; i++) {insertTime++;System.out.println("第" + insertTime + "次插入排序");//此處是簡(jiǎn)單插入排序//分組已排序序列的最后一個(gè)元素current = arr[i];//局部未排序序列的第一個(gè)元素int preIndex = i - incrementTime;//尋找當(dāng)前元素在分組有序序列中的相應(yīng)位置，未結(jié)束循環(huán)且分組有序序列前一個(gè)元素比當(dāng)前元素大，則繼續(xù)向前尋找while (preIndex >= 0 && arr[preIndex] > current) {//交換位置arr[preIndex + incrementTime] = arr[preIndex];//繼續(xù)尋找preIndex -= incrementTime;}//如果分組已排序序列已經(jīng)循環(huán)完畢，或者已經(jīng)找到對(duì)應(yīng)位置，則結(jié)束尋找arr[preIndex + incrementTime] = current;for (int value : arr) {System.out.print(value + " ");}System.out.println(" ");}}return arr;} }

運(yùn)行結(jié)果：

第1組5增量 第1次插入排序 10 2 8 3 6 8 4 7 9 1 第2次插入排序 10 2 8 3 4 6 8 7 9 1 第3次插入排序 10 2 8 3 4 6 7 8 9 1 第4次插入排序 10 2 8 3 4 6 7 8 9 1 第5次插入排序 1 10 2 8 3 4 6 7 8 9 第2組2增量 第1次插入排序 1 10 2 8 3 4 6 7 8 9 第2次插入排序 1 8 2 10 3 4 6 7 8 9 第3次插入排序 1 8 2 10 3 4 6 7 8 9 第4次插入排序 1 4 2 8 3 10 6 7 8 9 第5次插入排序 1 4 2 8 3 10 6 7 8 9 第6次插入排序 1 4 2 7 3 8 6 10 8 9 第7次插入排序 1 4 2 7 3 8 6 10 8 9 第8次插入排序 1 4 2 7 3 8 6 9 8 10 第3組1增量 第1次插入排序 1 4 2 7 3 8 6 9 8 10 第2次插入排序 1 4 2 7 3 8 6 9 8 10 第3次插入排序 1 4 2 7 3 8 6 9 8 10 第4次插入排序 1 3 2 7 4 8 6 9 8 10 第5次插入排序 1 3 2 7 4 8 6 9 8 10 第6次插入排序 1 3 2 6 4 8 7 9 8 10 第7次插入排序 1 3 2 6 4 8 7 9 8 10 第8次插入排序 1 3 2 6 4 8 7 9 8 10 第9次插入排序 1 3 2 6 4 8 7 9 8 10 結(jié)果 1 3 2 6 4 8 7 9 8 10

5、歸并排序

和選擇排序一樣，歸并排序的性能不受輸入數(shù)據(jù)的影響，但表現(xiàn)比選擇排序好的多，因?yàn)槭冀K都是O(n log n）的時(shí)間復(fù)雜度。代價(jià)是需要額外的內(nèi)存空間。

歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。歸并排序是一種穩(wěn)定的排序方法。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱(chēng)為2-路歸并。

?把長(zhǎng)度為n的輸入序列分成兩個(gè)長(zhǎng)度為n/2的子序列； ?對(duì)這兩個(gè)子序列分別采用歸并排序； ?將兩個(gè)排序好的子序列合并成一個(gè)最終的排序序列。

復(fù)雜度和穩(wěn)定性：

平均時(shí)間復(fù)雜度最差時(shí)間復(fù)雜度最優(yōu)時(shí)間復(fù)雜度空間復(fù)雜度穩(wěn)定性O(shè)(n log2 n)O(n log2 n)O(n log2 n)O(n)穩(wěn)定

歸并排序迭代版，Java代碼實(shí)現(xiàn)：

public class MergeSortIteration {public static void main(String[] args) {//TODO 歸并排序迭代版int[] arr = new int[]{10, 2, 8, 3, 6, 5, 4, 7, 9, 1};sort(arr);}public static void sort(int[] arr) {if (arr == null || arr.length < 2) {return;}int[] orderedArr = new int[arr.length];for (int i = 2; i < arr.length * 2; i *= 2) {for (int j = 0; j < (arr.length + i - 1) / i; j++) {int left = i * j;int mid = left + i / 2 >= arr.length ? (arr.length - 1) : (left + i / 2);int right = i * (j + 1) - 1 >= arr.length ? (arr.length - 1) : (i * (j + 1) - 1);int start = left, l = left, m = mid;while (l < mid && m <= right) {if (arr[l] < arr[m]) {orderedArr[start++] = arr[l++];} else {orderedArr[start++] = arr[m++];}}while (l < mid)orderedArr[start++] = arr[l++];while (m <= right)orderedArr[start++] = arr[m++];System.arraycopy(orderedArr, left, arr, left, right - left + 1);}}} }

歸并排序遞歸版，Java代碼實(shí)現(xiàn)：

public class MergeSortRecursive {public static void main(String[] args) {//TODO 歸并排序遞歸版int[] arr = new int[]{10, 2, 8, 3, 6, 5, 4, 7, 9, 1};sort(arr);}private static void sort(int[] arr) {if (arr == null || arr.length < 2) {return;}int[] result = new int[arr.length];merge_sort_recursive(arr, result, 0, arr.length - 1);}private static void merge_sort_recursive(int[] arr, int[] result, int start, int end) {if (start >= end)return;int len = end - start, mid = (len >> 1) + start;int start1 = start, end1 = mid;int start2 = mid + 1, end2 = end;merge_sort_recursive(arr, result, start1, end1);merge_sort_recursive(arr, result, start2, end2);int k = start;while (start1 <= end1 && start2 <= end2)result[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];while (start1 <= end1)result[k++] = arr[start1++];while (start2 <= end2)result[k++] = arr[start2++];for (k = start; k <= end; k++)arr[k] = result[k];} }

歡迎關(guān)注Android技術(shù)堆棧，專(zhuān)注于Android技術(shù)學(xué)習(xí)的公眾號(hào)，致力于提高Android開(kāi)發(fā)者們的專(zhuān)業(yè)技能！

總結(jié)

以上是生活随笔為你收集整理的合并两个无序数组java_Java实现十大排序算法（上）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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