【Java】排序算法

2019-11-06 07:34:04

字體：大中小

來源：轉載

供稿：網友

所有排序算法的基本原理無外乎將一個無序序列分為有序區（1個即有序）和無序區，然后不斷重復迭代將無序區的數放入有序區。

以下排序算法皆以升序為例：

一、窮舉法： 1.冒泡排序(Bubble Sort)：如圖大數往上頂，任意兩個相鄰數從無序到有序。

這里寫圖片描述

PRivate static void BubbleSort(int[] array){ for(int i = 0;i < array.length - 1;i++) for(int j = 0;j < array.length - 1 - i;j++) if(array[j + 1] < array[j]){ int temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; } }

2.插入排序(Insertion Sort)：如圖左側為有序區，右側無序區，將無序區的第一個元素插入到有序區合適的位置，重復過程。這里寫圖片描述

private static void InsertionSort(int[] array) { for (int i = 1; i < array.length; i++) { int j; int target = array[i]; for (j = i; j > 0 && target < array[j - 1];j--) { array[j] = array[j - 1]; } array[j] = target; } }

3.選擇排序(Selection Sort)：如圖左側為有序區，右側無序區。將無序區最小的元素與無序區的第一個元素對調，重復過程。這里寫圖片描述

private static void SelectionSort(int[] array) { //宏觀上：將無序區最小的元素與第一個元素對調 for(int i = 0; i < array.length; i++) { //微觀上：只要比基準元素小就與第一個元素對調 for(int j = i + 1; j < array.length; j++) { if(array[i] > array[j]) { int temp = array[j]; array[j] = array[i]; array[i] = temp; } } } }

二、分治法(Divide and Conquer)： 4.歸并排序(Merge Sort)：這里寫圖片描述

//排序 private static void MergeSort(int[] array, int low, int high) { int mid = (low + high) / 2; if (low < high) { MergeSort(array, low, mid);// 左邊 MergeSort(array, mid + 1, high);// 右邊 Merge(array, low, mid, high);// 左右歸并 } } //歸并 private static void Merge(int[] array, int low, int mid, int high) { int[] tempArray = new int[high - low + 1]; int leftLow = low;// 左開頭 int rightLow = mid + 1;// 右開頭 int i = 0; //將兩個要歸并的數組按序一個一個地移入新數組，知道某個數組被掏空 while (leftLow <= mid && rightLow <= high) { if (array[leftLow] < array[rightLow]) { tempArray[i++] = array[leftLow++]; } else { tempArray[i++] = array[rightLow++]; } } // 把左邊剩余的數移入數組 while (leftLow <= mid) { tempArray[i++] = array[leftLow++]; } // 把右邊邊剩余的數移入數組 while (rightLow <= high) { tempArray[i++] = array[rightLow++]; } // 把新數組中的數覆蓋給array數組 for (int j = 0; j < tempArray.length; j++) { array[j + low] = tempArray[j]; } }

5.快速排序(Quick Sort)：隨便找個基準數（一般取首或尾），小的放它左邊，大的放它右邊。對兩側的分區重復以上過程。其中的基準數就是有序區，兩側區間就是無序區。這里寫圖片描述

//返回分區后的中軸在序列中的位置 private static int getMiddle(int[] array, int low, int high) { int tmp = array[low]; //數組的第一個作為中軸 while (low < high) { //比中軸小的記錄移到低端 while (low < high && array[high] > tmp) { high--; } array[low] = array[high]; //比中軸大的記錄移到高端 while (low < high && array[low] < tmp) { low++; } array[high] = array[low]; } array[low] = tmp; //中軸記錄到尾 return low; //返回中軸的位置(介于兩個分區之間) } private static void QuickSort(int[] array, int low, int high) { if (low < high) { int middle = getMiddle(array, low, high); //將list數組進行一分為二 QuickSort(array, low, middle - 1); //對低字表進行遞歸排序 QuickSort(array, middle + 1, high); //對高字表進行遞歸排序 } }

上一篇：二、java-常用java驗證碼

下一篇：java之成績總結