import java.util.Arrays;
public class SortTest {
????public static void main(String... args) {
????????int[] arr = {12, 55, 22, 166, 2, 75, 30, 100, 200};
? ? ? ? bubbleSortArray(arr); //冒泡排序
? ? ? ? selectSortArray(arr); //選擇排序
? ? ? ? insertSortArray(arr); //插入排序
? ? ? ? shellSortArray(arr); //希爾排序
? ? ? ? quickSortArray(arr, 0, arr.length -1); //快速排序
? ? ? ? System.out.println("快速排序結(jié)果：" + Arrays.toString(arr));
? ? ? ? int[] arr2 =mergeSortArray(arr);
? ? ? ? System.out.println("歸并排序結(jié)果：" + Arrays.toString(arr2));
????}
????/**
? ? * 冒泡（Bubble）排序:效率 O（n2）,適用于排序小列表
? ? * 原理：比較兩個(gè)相鄰的元素跷究，將值大的元素交換至右端。
? ? * 思路：依次比較相鄰的兩個(gè)數(shù)，將小數(shù)放在前面，大數(shù)放在后面晕翠。
? ? * 即在第一趟：首先比較第1個(gè)和第2個(gè)數(shù)遍尺，將小數(shù)放前，大數(shù)放后诗祸。
? ? * 然后比較第2個(gè)數(shù)和第3個(gè)數(shù)血久，將小數(shù)放前突照，大數(shù)放后，
? ? * 如此繼續(xù)洋魂，直至比較最后兩個(gè)數(shù)，將小數(shù)放前喜鼓，大數(shù)放后副砍。
? ? * 重復(fù)第一趟步驟，直至全部排序完成庄岖。
? ? *
? ? * @param arr
? ? * @return void
????*/
????private static void bubbleSortArray(int[] arr) {
????????int len = arr.length;
? ? ? ? for (int i =1; i < len; i++) {
????????????for (int j =0; j < len - i; j++) {
????????????????if (arr[j] > arr[j +1]) {?//比較交換相鄰元素
? ? ? ? ? ? ? ? ? ? int temp;
? ? ? ? ? ? ? ? ? ? temp = arr[j];
? ? ? ? ? ? ? ? ? ? arr[j] = arr[j +1];
? ? ? ? ? ? ? ? ? ? arr[j +1] = temp;
? ? ? ? ? ? ? ? }
????????????}
????????}
????????System.out.println("冒泡排序結(jié)果：" + Arrays.toString(arr));
????}
????/**
? ? * 選擇排序:效率O（n2）豁翎，適用于排序小的列表
? ? * 原理：每一趟從待排序的記錄中選出最小的元素，順序放在已排好序的序列最后隅忿，直到全部記錄排序完畢心剥。
? ? * 也就是：每一趟在n-i+1(i=1，2背桐，…n-1)個(gè)記錄中選取關(guān)鍵字最小的記錄作為有序序列中第i個(gè)記錄优烧。
? ? * 基于此思想的算法主要有簡(jiǎn)單選擇排序、樹型選擇排序和堆排序链峭。
? ? * 思路：給定數(shù)組 int[] arr={里面n個(gè)數(shù)據(jù)}畦娄；
? ? * 第1趟排序，在待排序數(shù)據(jù)arr[1]~arr[n]中選出最小的數(shù)據(jù)弊仪，將它與arr[1]交換熙卡；
? ? * 第2趟，在待排序數(shù)據(jù)arr[2]~arr[n]中選出最小的數(shù)據(jù)励饵，將它與r[2]交換驳癌；
? ? * 以此類推，第i趟在待排序數(shù)據(jù)arr[i]~arr[n]中選出最小的數(shù)據(jù)役听，將它與r[i]交換颓鲜，直到全部排序完成表窘。
? ? *
? ? * @param arr
? ? * @return void
????*/
? ? private static void selectSortArray(int[] arr) {
????????int len = arr.length;
? ? ? ? int minIndex;
? ? ? ? for (int i =0; i < len -1; i++) {
????????????minIndex = i;
? ? ? ? ? ? for (int j = i +1; j < len; j++) {
????????????????if (arr[j] < arr[minIndex]) minIndex = j; //記下目前找到的最小值所在的位置
????????????}
? ??????????if (minIndex != i) {
????????????????????//找到最小項(xiàng)交換，將這一項(xiàng)移到列表中的正確位置
? ? ? ? ? ? ? ? ? ? int temp;
? ? ? ? ? ? ? ? ? ? temp = arr[i];
? ? ? ? ? ? ? ? ? ? arr[i] = arr[minIndex];
? ? ? ? ? ? ? ? ? ? arr[minIndex] = temp;
? ? ? ? ? ? ? ? }
????????}
????????System.out.println("選擇排序結(jié)果：" + Arrays.toString(arr));
? ? }
????/**
? ? * 插入排序:最佳效率O（n）灾杰；最糟效率O（n2）與冒泡蚊丐、選擇相同，適用于排序小列表 ;若列表基本有序艳吠，則插入排序比冒泡麦备、選擇更有效率。
? ? * 原理：每插入一個(gè)數(shù)都要將它和之前的已經(jīng)完成排序的序列進(jìn)行重新排序昭娩，也就是要找到新插入的數(shù)對(duì)應(yīng)原序列中的位置凛篙。
? ? * 就是說(shuō)，每次插入一個(gè)數(shù)都要對(duì)原來(lái)排序好的那部分序列進(jìn)行重新的排序栏渺，時(shí)間復(fù)雜度同樣為O（n2）呛梆。
? ? * 這種算法是穩(wěn)定的排序方法。
? ? *
? ? * @param arr
? ? */
? ? private static void insertSortArray(int[] arr) {
????????int len = arr.length;
? ? ? ? for (int i =1; i < len; i++) {
????????????//循環(huán)從第二個(gè)數(shù)組元素開始磕诊，因?yàn)閍rr[0]作為最初已排序部分
? ? ? ? ? ? int temp = arr[i]; //temp標(biāo)記為未排序第一個(gè)元素
? ? ? ? ? ? int j = i -1;
? ? ? ? ? ? while (j >=0 && arr[j] > temp) {
????????????????//將temp與已排序元素從小到大比較填物，尋找temp應(yīng)插入的位置
? ? ? ? ? ? ? ? arr[j +1] = arr[j];
? ? ? ? ? ? ? ? j--;
? ? ? ? ? ? }
????????????arr[j +1] = temp;
? ? ? ? }
????????System.out.println("插入排序結(jié)果：" + Arrays.toString(arr));
? ? }
????/**
? ? * 希爾排序：縮小增量排序，適用于排序小列表霎终。
? ? * 效率估計(jì)O（nlog2^n）~O（n^1.5）滞磺，取決于增量值的最初大小。
? ? * 建議使用質(zhì)數(shù)作為增量值莱褒，因?yàn)槿绻隽恐凳?的冪击困，則在下一個(gè)通道中會(huì)再次比較相同的元素。
? ? * 希爾排序改進(jìn)了插入排序广凸，減少了比較的次數(shù)阅茶。是不穩(wěn)定的排序，因?yàn)榕判蜻^(guò)程中元素可能會(huì)前后跳躍谅海。
? ? * 思想：先將整個(gè)待排記錄序列分割成為若干子序列分別進(jìn)行直接插入排序脸哀，
? ? * 待整個(gè)序列中的記錄“基本有序”時(shí)，在對(duì)全體進(jìn)行一次直接插入排序扭吁。
? ? * 思路：設(shè)待排序元素序列有n個(gè)元素企蹭，首先取一個(gè)整數(shù)increment（小于n）作為間隔將全部元素分為increment個(gè)子序列，
? ? * 所有距離為increment的元素放在同一個(gè)子序列中智末，在每一個(gè)子序列中分別實(shí)行直接插入排序谅摄。
? ? * 然后縮小間隔increment，重復(fù)上述子序列劃分和排序工作系馆。直到最后取increment=1送漠，將所有元素放在同一個(gè)子序列中排序?yàn)橹埂?/p>
? ? * 由于開始時(shí)，increment的取值較大由蘑，每個(gè)子序列中的元素較少闽寡，排序速度較快代兵，到排序后期increment取值逐漸變小，
? ? * 子序列中元素個(gè)數(shù)逐漸增多爷狈，由于前面大多數(shù)元素已經(jīng)基本有序植影，所以排序速度仍然很快。
? ? *
? ? * @param arr
? ? */
? ? private static void shellSortArray(int[] arr) {
????????int len = arr.length;
? ? ? ? for (int incr =3; incr >0; incr--) {
????????????//增量遞減涎永，以增量3思币，2，1為例
? ? ? ? ? ? for (int l =0; l < (len -1) / incr; l++) {
????????????????//重復(fù)分成的每個(gè)子列表
? ? ? ? ? ? ? ? for (int i = l + incr; i < len; i += incr) {
????????????????????//對(duì)每個(gè)子列表應(yīng)用插入排序
? ? ? ? ? ? ? ? ? ? int temp = arr[i];
? ? ? ? ? ? ? ? ? ? int j = i - incr;
? ? ? ? ? ? ? ? ? ? while (j >=0 && arr[j] > temp) {
????????????????????????arr[j + incr] = arr[j];
? ? ? ? ? ? ? ? ? ? ? ? j -= incr;
? ? ? ? ? ? ? ? ? ? }
????????????????????arr[j + incr] = temp;
? ? ? ? ? ? ? ? }
????????????}
? ? ? ? }
????????System.out.println("希爾排序結(jié)果：" + Arrays.toString(arr));
? ? }
????/**
? ? * 快速排序：在快速排序中羡微，相等元素可能會(huì)因?yàn)榉謪^(qū)而交換順序谷饿，所以它是不穩(wěn)定的算法。
? ? * 思想：通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分：分割點(diǎn)左邊都是比它小的數(shù)妈倔，右邊都是比它大的數(shù)博投。
? ? * 然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行盯蝴，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列毅哗。
? ? * 時(shí)間復(fù)雜度：數(shù)據(jù)越隨機(jī)分布時(shí)，快速排序性能越好捧挺；數(shù)據(jù)越接近有序虑绵，快速排序性能越差。
? ? * 快速排序的時(shí)間復(fù)雜度在最壞情況下是O(N2)松忍，平均的時(shí)間復(fù)雜度是O(N*lgN)蒸殿。
? ? * 空間復(fù)雜度：快速排序在每次分割的過(guò)程中筷厘，需要1個(gè)空間存儲(chǔ)基準(zhǔn)值鸣峭。而快速排序的大概需要Nlog2N次的分割處理，占用空間也是Nlog2N個(gè)酥艳。
? ? *
? ? * @param arr
? ? * @param left? 數(shù)組的左邊界(例如摊溶，從起始位置開始排序，則left=0)
? ? * @param right 數(shù)組的右邊界(例如充石，排序截至到數(shù)組末尾莫换，則right=a.length-1)
????*/
? ? private static void quickSortArray(int[] arr, int left, int right) {
????????if (left < right) {
????????????int i, j, k;
? ? ? ? ? ? i = left;
? ? ? ? ? ? j = right;
? ? ? ? ? ? k = arr[i];
? ? ? ? ? ? while (i < j) {
????????????????while (i < j && arr[j] > k) j--; //從右向左找第一個(gè)小于k的數(shù)
? ? ? ? ? ? ? ? if (i < j) arr[i++] = arr[j];
? ? ? ? ? ? ? ? while (i < j && arr[i] < k) i++; //從左向右找第一個(gè)大于k的數(shù)
? ? ? ? ? ? ? ? if (i < j) arr[j--] = arr[i];
? ? ? ? ? ? }
????????????arr[j] = k;
? ? ? ? ? ? quickSortArray(arr, left, i -1); //遞歸調(diào)用
? ? ? ? ? ? quickSortArray(arr, i +1, right); //遞歸調(diào)用
? ? ? ? }
????}
????/**
? ? * 歸并排序：
? ? * 思想：將待排序元素分成大小大致相同的2個(gè)子集合，分別對(duì)2個(gè)子集合進(jìn)行排序骤铃，最終將排好序的子集合合并成為所要求的排序集合拉岁。
? ? * @param arr
? ? * @return
? ? */
? ? private static int[]mergeSortArray(int[] arr) {
????????for (int gap =1; gap < arr.length; gap =2 * gap) {
????????????int i =0;
? ? ? ? ? ? // 歸并gap長(zhǎng)度的兩個(gè)相鄰子表
? ? ? ? ? ? for (i =0; i +2 * gap -1 < arr.length; i +=2 * gap)
????????????????merge(arr, i, i + gap -1, i +2 * gap -1);
? ? ? ? ? ? // 余下兩個(gè)子表，后者長(zhǎng)度小于gap
? ? ? ? ? ? if (i + gap -1 < arr.length)
????????????????merge(arr, i, i + gap -1, arr.length -1);
? ? ? ? }
????????return arr;
? ? }
????private static void merge(int[] arr, int low, int mid, int high) {
????????int i = low; // i是第一段序列的下標(biāo)
? ? ? ? int j = mid +1; // j是第二段序列的下標(biāo)
? ? ? ? int k =0; // k是臨時(shí)存放合并序列的下標(biāo)
? ? ? ? int[] arr2 =new int[high - low +1]; //arr2是臨時(shí)合并序列
? ? ? ? // 掃描第一段和第二段序列惰爬，直到有一個(gè)掃描結(jié)束
? ? ? ? while (i <= mid && j <= high) {
????????????// 判斷第一段和第二段取出的數(shù)哪個(gè)更小喊暖，將其存入合并序列，并繼續(xù)向下掃描
? ? ? ? ? ? if (arr[i] <= arr[j]) {
????????????????arr2[k] = arr[i];
? ? ? ? ? ? ? ? i++;
? ? ? ? ? ? ? ? k++;
? ? ? ? ? ? } else {
????????????????arr2[k] = arr[j];
? ? ? ? ? ? ? ? j++;
? ? ? ? ? ? ? ? k++;
? ? ? ? ? ? }
????????}
????????// 若第一段序列還沒(méi)掃描完撕瞧，將其全部復(fù)制到合并序列
? ? ? ? while (i <= mid) {
????????????arr2[k] = arr[i];
? ? ? ? ? ? i++;
? ? ? ? ? ? k++;
? ? ? ? }
????????// 若第二段序列還沒(méi)掃描完陵叽，將其全部復(fù)制到合并序列
? ? ? ? while (j <= high) {
????????????arr2[k] = arr[j];
? ? ? ? ? ? j++;
? ? ? ? ? ? k++;
? ? ? ? }
????????// 將合并序列復(fù)制到原始序列中
? ? ? ? for (k =0, i = low; i <= high; i++, k++) arr[i] = arr2[k];
? ? }
}
運(yùn)行結(jié)果：
冒泡排序結(jié)果：[2, 12, 22, 30, 55, 75, 100, 166, 200]
選擇排序結(jié)果：[2, 12, 22, 30, 55, 75, 100, 166, 200]
插入排序結(jié)果：[2, 12, 22, 30, 55, 75, 100, 166, 200]
希爾排序結(jié)果：[2, 12, 22, 30, 55, 75, 100, 166, 200]
快速排序結(jié)果：[2, 12, 22, 30, 55, 75, 100, 166, 200]
歸并排序結(jié)果：[2, 12, 22, 30, 55, 75, 100, 166, 200]
