文章目錄

• • • 冒泡排序
    • 選擇排序
    • 插入排序
    • 希爾排序

冒泡排序

??第一個元素開始向第二個元素比較，若大于則交換位置，不大于則不動。然后第二個元素和第三個元素比較，再然后第三個元素和第四個元素比較…一直比到最后一個元素。這一趟下來，就把最大的元素放到了最后。
??然后又從第一個元素開始，開始第二趟…然后開始第三趟…一直走完最后一趟。

package com.serein.sort;import java.util.Arrays;/*** @author baichuan* @version 1.0*/ public class BubbleSort {public static void main(String[] args) { // int[] arr = {3,10,5,7,-1};int[] arr = new int[80000];for (int i = 0; i < 80000; i++) {arr[i] = (int) (Math.random()*800000);}long millisStart = System.currentTimeMillis();bubble(arr);long millisEnd = System.currentTimeMillis();System.out.println("一共耗時：" + (millisEnd - millisStart)/1000 + " 秒");//把排序結(jié)果打印出來看看System.out.println(Arrays.toString(arr));}private static void bubble(int[] arr){int temp = 0;boolean flag = false;//這樣的排序一共執(zhí)行 arr.length - 1次for (int j = 0;j < arr.length - 1;j++) {//因為后面的元素已經(jīng)確定是更大的數(shù)，遍歷的時候沒必要再走過去判斷畫蛇添足for (int i = 0; i < arr.length - 1 - j; i++) {//若前面的數(shù)字比后面的大，交換大小if (arr[i] > arr[i + 1]){flag = true;temp = arr[i];arr[i] = arr[i + 1];arr[i + 1] = temp;}}//如果若前面的數(shù)字比后面的小，那就不必再判，退出當(dāng)前循環(huán)if (!flag){break;}else {flag = false;}}} }

測試截圖

選擇排序

??先定義一個索引，把它指向第一個元素。讓第一個元素和第二個比較。若第二個小，就把索引指向第二個元素；若不是，索引不動。然后把索引指向的元素和第三個元素比較，更新索引位置。然后和第四個元素比較…以此類推，一直比到最后一個元素，然后把索引指向的元素和第一個元素換位置。這一趟下來就把最小的元素放到了最前面。
??然后就從第二個元素開始重復(fù)上述步驟，這一趟下來把第二小的元素放到了第二個位置…以此類推，直到最后一個元素。
??和冒泡排序相比，一趟下來，冒泡排序每一步都在交換位置；而選擇排序一趟只換了一次位置。

package com.serein.sort;import java.util.Arrays;/*** @author baichuan* @version 1.0*/ public class SelectSort {public static void main(String[] args) { // int[] arr = {50,999,6,3};int[] arr = new int[80000];for (int i = 0; i < 80000; i++) {arr[i] = (int) (Math.random()*800000);}long millisStart = System.currentTimeMillis();select(arr);long millisEnd = System.currentTimeMillis();System.out.println("一共耗時：" + (millisEnd - millisStart)/1000.00 + " 秒");System.out.println(Arrays.toString(arr));}public static void select(int[] arr) {int minIndex = 0;//單簽最小值的索引int min = arr[0];//當(dāng)前最小值，先假定第一個元素使最小的，然后執(zhí)行邏輯判斷boolean flag = false;for (int j = 0; j < arr.length - 1; j++) {minIndex = j;min = arr[j];//先完成一輪操作，找規(guī)律，然后在外面嵌套一層for循環(huán)幫我們做事for (int i = j + 1; i < arr.length; i++) {if (min > arr[i]) {flag = true;min = arr[i];minIndex = i;}}//把最小值放到arr[j],即交換。最開始就是arr[0],即第一個位置，第二次for循環(huán)是就是第二個位置//以此類推，以j為分界線，每次都找出當(dāng)前最小的放到分界線末尾，一直把分界線推到數(shù)組最后if (!flag) {//如果min 沒有大于arr[i]，那就不用再交換位置了，退出本次循環(huán)break;}else {flag = false;}arr[minIndex] = arr[j];arr[j] = min;}} }

插入排序

??把一個數(shù)組視為有序列表和無序列表兩部分。
??初始來說，有序列表就是數(shù)組的第一個元素，后面的所有元素是無序列表，待插入元素就是數(shù)組第二個元素。我們要做的就是把無序列表的數(shù)一個一個放到有序列表里。
??走一輪，把第二個元素放入有序列表并比大小，有序列表就有兩個元素了。后面的所有元素是無序列表，待插入元素就是數(shù)組第三個元素，以此類推
??我們站在待插入元素的位置上看待問題，核心就是給待插入元素找位置。

package com.serein.sort;import java.util.Arrays;/*** @author baichuan* @version 1.0*/ public class InsertSort {public static void main(String[] args) { // int[] arr = {66,4,5,1};int[] arr = new int[80000];for (int i = 0; i < 80000; i++) {arr[i] = (int) (Math.random()*800000);}long millisStart = System.currentTimeMillis();insert(arr);long millisEnd = System.currentTimeMillis();System.out.println("一共耗時：" + (millisEnd - millisStart)/1000.00 + " 秒");System.out.println(Arrays.toString(arr));}//初始來說，有序列表就是數(shù)組的第一個元素，后面的所有元素是無序列表，待插入元素就是數(shù)組第二個元素//走一輪，有序列表就有兩個元素了，后面的所有元素是無序列表，待插入元素就是數(shù)組第三個元素，以此類推//我們站在待插入元素的位置上看待問題，核心就是給待插入元素找位置private static void insert(int[] arr){int insertIndex = 0;//待插入元素的索引int insertValue = 0;//把待插入元素的值for (int i = 1; i < arr.length; i++) {insertIndex = i- 1;//待插入元素的默認索引為，加到序列表的最后面insertValue = arr[i];//把待插入元素的值保存起來//先和有序列表的第一個元素比較，如果不行就往后比較while(insertIndex >= 0 && insertValue < arr[insertIndex]){//如果待插入元素的值比原有序列表的最后一個元素要小，就把有序列表（有序列表是定義在心中的）擴容一位，//并且把這個元素的值賦給新增的位置（說明：我們只定義了一個數(shù)組，這時//有序列表和無序列表是此消彼長的零和博弈，我們要的就是此消彼長。）arr[insertIndex + 1] = arr[insertIndex];//第一次插入元素上述流程只走一遍的話即可，到后面索引還要往前撥，//判斷待插入元素比有序列表倒數(shù)第二個元素的大小...然后再判斷和倒數(shù)第三個元素的大小，以此類推//一個待插入元素第二次及以上找位置時，復(fù)制元素就不是和無序列表搶位置的//此消彼長了，而是有序列表的內(nèi)斗。無序列表不受影響。insertIndex--;}//退出while循環(huán)，說明找到了位置，我們把待插入元素的值賦給該索引。arr[insertIndex + 1] = insertValue;}} }

測試截圖

希爾排序

??在插入排序的基礎(chǔ)上，先按步長先分組調(diào)位置，使得在插入排序前在宏觀上大致有序，提高了插入排序的效率。步長逐步縮小，叫做縮小增量。

package com.serein.sort;import java.util.Arrays;/*** @author baichuan* @version 1.0*/ public class ShellSort {public static void main(String[] args) { // int[] arr = {8,9,1,7,2,3,5,4,6,0};int[] arr = new int[80000];for (int i = 0; i < 80000; i++) {arr[i] = (int) (Math.random()*800000);}long millisStart = System.currentTimeMillis(); // shell(arr);shell2(arr);long millisEnd = System.currentTimeMillis();System.out.println("一共耗時：" + (millisEnd - millisStart) + " 毫秒");System.out.println("希爾牛皮！！！");System.out.println(Arrays.toString(arr));}private static void shell(int[] arr){int temp = 0;//交換元素需要的臨時變量，定義在循環(huán)外面可節(jié)省開銷//gap是步長，初始化為數(shù)組長度的一半，每次循環(huán)都讓步長減半。減到1組的時候循環(huán)會結(jié)束for (int gap = arr.length / 2;gap > 0;gap /= 2){//分出有多少組步長for (int i = gap; i < arr.length; i++) {//走一次就是判斷一組步長，因為i的變化會使得走完所有組for (int j = i - gap; j >= 0 ; j -= gap){//若前面的數(shù)大于步長后面的數(shù)，則位置互換if (arr[j] > arr[j + gap]){temp = arr[j];arr[j] = arr[j + gap];arr[j + gap] = temp;}}}}}//上面那個是交換式希爾排序，由于交換次數(shù)較多，所以耗時也比較久。//以下采用移位式希爾排序//對比private static void shell2(int[] arr){for (int gap = arr.length / 2; gap > 0; gap /= 2){//分出有多少組步長for (int i = gap; i < arr.length; i++) {int j = i;int temp = arr[j];//定義臨時變量保存一組步長后面那個數(shù)//引入索引的概念，減少了交換次數(shù)。這是提高效率的核心！！！ // if (arr[j] < arr[j - gap]){//如果后面那個數(shù)更小，就先把前面的數(shù)復(fù)制一份到后面那個數(shù)while (j - gap >= 0 && temp < arr[j - gap]){//上面的if判斷似乎多余，這里就起到了判斷一組步長前后元素大小的作用arr[j] = arr[j - gap];//讓j指向前面的數(shù)j -= gap;}//把原始后面那個數(shù)賦給步長前面那個數(shù)arr[j] = temp; // }}}} }

總結(jié)

以上是生活随笔為你收集整理的【排序算法】冒泡排序|选择排序|插入排序|希尔排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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