冒泡排序

import java.util.Arrays;public class BubbleSort {public static void sort(int array[]){int tmp = 0;//記錄最后一次交換的位置int lastExchangeIndex = 0;//無序數列的邊界，每次比較只需要比到這里為止int sortBorder = array.length - 1;for(int i = 0; i < array.length; i++){//有序標記，每一輪的初始是trueboolean isSorted = true;for(int j = 0; j < sortBorder; j++){if(array[j] > array[j+1]){tmp = array[j];array[j] = array[j+1];array[j+1] = tmp;//有元素交換，所以不是有序，標記變為falseisSorted = false;//把無序數列的邊界更新為最后一次交換元素的位置lastExchangeIndex = j;}}sortBorder = lastExchangeIndex;if(isSorted){break;}}}public static void main(String[] args){int[] array = new int[]{3,4,2,1,5,6,7,8};sort(array);System.out.println(Arrays.toString(array));} }

雞尾酒排序

import java.util.Arrays;public class CockTailSort {public static void sort(int array[]){int tmp = 0;for(int i=0; i<array.length/2; i++){//有序標記，每一輪的初始是trueboolean isSorted = true;//奇數輪，從左向右比較和交換for(int j=i; j<array.length-i-1; j++){if(array[j] > array[j+1]){tmp = array[j];array[j] = array[j+1];array[j+1] = tmp;//有元素交換，所以不是有序，標記變為falseisSorted = false;}}if(isSorted){break;}//偶數輪之前，重新標記為trueisSorted = true;//偶數輪，從右向左比較和交換for(int j=array.length-i-1; j>i; j--){if(array[j] < array[j-1]){tmp = array[j];array[j] = array[j-1];array[j-1] = tmp;//有元素交換，所以不是有序，標記變為falseisSorted = false;}}if(isSorted){break;}}}public static void main(String[] args){int[] array = new int[]{2,3,4,5,6,7,8,1};sort(array);System.out.println(Arrays.toString(array));} }

快速排序

import java.util.Arrays;public class QuickSort {public static void quickSort(int[] arr, int startIndex, int endIndex) {// 遞歸結束條件：startIndex大等于endIndex的時候if (startIndex >= endIndex) {return;}// 得到基準元素位置int pivotIndex = partition(arr, startIndex, endIndex);// 根據基準元素，分成兩部分遞歸排序quickSort(arr, startIndex, pivotIndex - 1);quickSort(arr, pivotIndex + 1, endIndex);}/*** 分治（雙邊循環法）* @param arr 待交換的數組* @param startIndex 起始下標* @param endIndex 結束下標*/private static int partition(int[] arr, int startIndex, int endIndex) {// 取第一個位置的元素作為基準元素（也可以選擇隨機位置）int pivot = arr[startIndex];int left = startIndex;int right = endIndex;while( left != right) {//控制right指針比較并左移while(left<right && arr[right] > pivot){right--;}//控制left指針比較并右移while( left<right && arr[left] <= pivot) {left++;}//交換left和right指向的元素if(left<right) {int p = arr[left];arr[left] = arr[right];arr[right] = p;}}//pivot和指針重合點交換arr[startIndex] = arr[left];arr[left] = pivot;return left;}/*** 分治（單邊循環法）* @param arr 待交換的數組* @param startIndex 起始下標* @param endIndex 結束下標*/private static int partitionV2(int[] arr, int startIndex, int endIndex) {// 取第一個位置的元素作為基準元素（也可以選擇隨機位置）int pivot = arr[startIndex];int mark = startIndex;for(int i=startIndex+1; i<=endIndex; i++){if(arr[i]<pivot){mark ++;int p = arr[mark];arr[mark] = arr[i];arr[i] = p;}}arr[startIndex] = arr[mark];arr[mark] = pivot;return mark;}public static void main(String[] args) {int[] arr = new int[] {4,4,6,5,3,2,8,1};quickSort(arr, 0, arr.length-1);System.out.println(Arrays.toString(arr));} }

使用棧快速排序

import java.util.Arrays; import java.util.HashMap; import java.util.Map; import java.util.Stack;public class QuickSortWithStack {public static void quickSort(int[] arr, int startIndex, int endIndex) {// 用一個集合棧來代替遞歸的函數棧Stack<Map<String, Integer>> quickSortStack = new Stack<Map<String, Integer>>();// 整個數列的起止下標，以哈希的形式入棧Map rootParam = new HashMap();rootParam.put("startIndex", startIndex);rootParam.put("endIndex", endIndex);quickSortStack.push(rootParam);// 循環結束條件：棧為空時結束while (!quickSortStack.isEmpty()) {// 棧頂元素出棧，得到起止下標Map<String, Integer> param = quickSortStack.pop();// 得到基準元素位置int pivotIndex = partition(arr, param.get("startIndex"), param.get("endIndex"));// 根據基準元素分成兩部分, 把每一部分的起止下標入棧if(param.get("startIndex") < pivotIndex -1){Map<String, Integer> leftParam = new HashMap<String, Integer>();leftParam.put("startIndex", param.get("startIndex"));leftParam.put("endIndex", pivotIndex -1);quickSortStack.push(leftParam);}if(pivotIndex + 1 < param.get("endIndex")){Map<String, Integer> rightParam = new HashMap<String, Integer>();rightParam.put("startIndex", pivotIndex + 1);rightParam.put("endIndex", param.get("endIndex"));quickSortStack.push(rightParam);}}}/*** 分治（單邊循環法）* @param arr 待交換的數組* @param startIndex 起始下標* @param endIndex 結束下標*/private static int partition(int[] arr, int startIndex, int endIndex) {// 取第一個位置的元素作為基準元素（也可以選擇隨機位置）int pivot = arr[startIndex];int mark = startIndex;for(int i=startIndex+1; i<=endIndex; i++){if(arr[i]<pivot){mark ++;int p = arr[mark];arr[mark] = arr[i];arr[i] = p;}}arr[startIndex] = arr[mark];arr[mark] = pivot;return mark;}public static void main(String[] args) {int[] arr = new int[] {4,7,6,5,3,2,8,1};quickSort(arr, 0, arr.length-1);System.out.println(Arrays.toString(arr));}}

堆排序

import java.util.Arrays;public class HeapSort {/*** 下沉調整* @param array 待調整的堆* @param parentIndex 要下沉的父節點* @param length 堆的有效大小*/public static void downAdjust(int[] array, int parentIndex, int length) {// temp保存父節點值，用于最后的賦值int temp = array[parentIndex];int childIndex = 2 * parentIndex + 1;while (childIndex < length) {// 如果有右孩子，且右孩子大于左孩子的值，則定位到右孩子if (childIndex + 1 < length && array[childIndex + 1] > array[childIndex]) {childIndex++;}// 如果父節點大于等于任何一個孩子的值，直接跳出if (temp >= array[childIndex])break;//無需真正交換，單向賦值即可array[parentIndex] = array[childIndex];parentIndex = childIndex;childIndex = 2 * childIndex + 1;}array[parentIndex] = temp;}/*** 堆排序(升序)* @param array 待調整的堆*/public static void heapSort(int[] array) {// 1.把無序數組構建成最大堆。for (int i = (array.length-2)/2; i >= 0; i--) {downAdjust(array, i, array.length);}System.out.println(Arrays.toString(array));// 2.循環交換集合尾部元素到堆頂，并調節堆產生新的堆頂。for (int i = array.length - 1; i > 0; i--) {// 最后一個元素和第一元素進行交換int temp = array[i];array[i] = array[0];array[0] = temp;// 下沉調整最大堆downAdjust(array, 0, i);}}public static void main(String[] args) {int[] arr = new int[] {1,3,2,6,5,7,8,9,10,0};heapSort(arr);System.out.println(Arrays.toString(arr));} }

桶排序

import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.LinkedList;public class BucketSort {public static double[] bucketSort(double[] array){//1.得到數列的最大值和最小值，并算出差值ddouble max = array[0];double min = array[0];for(int i=1; i<array.length; i++) {if(array[i] > max) {max = array[i];}if(array[i] < min) {min = array[i];}}double d = max - min;//2.初始化桶int bucketNum = array.length;ArrayList<LinkedList<Double>> bucketList = new ArrayList<LinkedList<Double>>(bucketNum);for(int i = 0; i < bucketNum; i++){bucketList.add(new LinkedList<Double>());}//3.遍歷原始數組，將每個元素放入桶中for(int i = 0; i < array.length; i++){int num = (int)((array[i] - min) * (bucketNum-1) / d);bucketList.get(num).add(array[i]);}//4.對每個桶內部進行排序for(int i = 0; i < bucketList.size(); i++){//JDK底層采用了歸并排序或歸并的優化版本Collections.sort(bucketList.get(i));}//5.輸出全部元素double[] sortedArray = new double[array.length];int index = 0;for(LinkedList<Double> list : bucketList){for(double element : list){sortedArray[index] = element;index++;}}return sortedArray;}public static void main(String[] args) {double[] array = new double[] {4.12,6.421,0.0023,3.0,2.123,8.122,4.12, 10.09};double[] sortedArray = bucketSort(array);System.out.println(Arrays.toString(sortedArray));} }

計數排序

import java.util.Arrays;public class CountSort {public static int[] countSort(int[] array) {//1.得到數列的最大值int max = array[0];for(int i=1; i<array.length; i++){if(array[i] > max){max = array[i];}}//2.根據數列最大值確定統計數組的長度int[] countArray = new int[max+1];//3.遍歷數列，填充統計數組for(int i=0; i<array.length; i++){countArray[array[i]]++;}//4.遍歷統計數組，輸出結果int index = 0;int[] sortedArray = new int[array.length];for(int i=0; i<countArray.length; i++){for(int j=0; j<countArray[i]; j++){sortedArray[index++] = i;}}return sortedArray;}public static int[] countSortV2(int[] array) {//1.得到數列的最大值和最小值，并算出差值dint max = array[0];int min = array[0];for(int i=1; i<array.length; i++) {if(array[i] > max) {max = array[i];}if(array[i] < min) {min = array[i];}}int d = max - min;//2.創建統計數組并統計對應元素個數int[] countArray = new int[d+1];for(int i=0; i<array.length; i++) {countArray[array[i]-min]++;}//3.統計數組做變形，后面的元素等于前面的元素之和for(int i=1;i<countArray.length;i++) {countArray[i] += countArray[i-1];}//4.倒序遍歷原始數列，從統計數組找到正確位置，輸出到結果數組int[] sortedArray = new int[array.length];for(int i=array.length-1;i>=0;i--) {sortedArray[countArray[array[i]-min]-1]=array[i];countArray[array[i]-min]--;}return sortedArray;}public static void main(String[] args) {int[] array = new int[] {4,4,6,5,3,2,8,1,7,5,6,0,10};int[] sortedArray = countSort(array);System.out.println(Arrays.toString(sortedArray));array = new int[] {95,94,91,98,99,90,99,93,91,92};sortedArray = countSort(array);System.out.println(Arrays.toString(sortedArray));} }

選擇排序

import java.util.Arrays;public class SelectionSort {public static void selectionSort(int[] array) {for (int i = 0; i < array.length - 1; i++) {int minIndex = i;for (int j = i + 1; j < array.length; j++) {if (array[j] < array[minIndex]) {minIndex = j;}}if (i != minIndex) {int temp = array[i];array[i] = array[minIndex];array[minIndex] = temp;}}}public static void main(String[] args) {int[] array = new int[] {3, 4, 2, 1, 5, 6, 7, 8, 30, 50, 1, 33, 24, 5, -4, 7, 0};selectionSort(array);System.out.println(Arrays.toString(array));} }

插入排序

import java.util.Arrays;public class InsertionSort {public static void insertSort(int[] array) {for (int i = 1; i < array.length; i++) {int insertValue = array[i];int j = i - 1;//從右向左比較元素的同時，進行元素復制for (; (j >= 0) && (insertValue < array[j]); j--) {array[j + 1] = array[j];}//insertValue的值插入適當位置array[j + 1] = insertValue;}}public static void main(String[] args) {int[] array = { 12, 1, 3, 46, 5, 0, -3, 12, 35, 16 };insertSort(array);System.out.println(Arrays.toString(array));} }

希爾排序

import java.util.Arrays;public class ShellSort {public static void shellSort(int[] array) {//希爾排序的增量int d = array.length;while (d > 1) {//使用希爾增量的方式，即每次折半d = d / 2;for (int x = 0; x < d; x++) {for (int i = x + d; i < array.length; i = i + d) {int temp = array[i];int j;for (j = i - d; (j >= 0) && (array[j] > temp); j = j - d) {array[j + d] = array[j];}array[j + d] = temp;}}}}public static void main(String[] args) {int[] array = { 5, 3, 9, 12, 6, 1, 7, 2, 4, 11, 8, 10 };shellSort(array);System.out.println(Arrays.toString(array));} }

歸并排序

import java.util.Arrays;public class MergeSort {public static void mergeSort(int[] array, int start, int end) {if (start < end) {//折半成兩個小集合，分別進行遞歸int mid = (start + end) / 2;mergeSort(array, start, mid);mergeSort(array, mid + 1, end);//把兩個有序小集合，歸并成一個大集合merge(array, start, mid, end);}}private static void merge(int[] array, int start, int mid, int end) {//開辟額外大集合，設置指針int[] tempArray = new int[end - start + 1];int p1 = start;int p2 = mid + 1;int p = 0;//比較兩個小集合的元素，依次放入大集合while ((p1 <= mid) && (p2 <= end)) {if (array[p1] <= array[p2]) {tempArray[p++] = array[p1++];}else {tempArray[p++] = array[p2++];}}//左側小集合還有剩余，依次放入大集合尾部while (p1 <= mid) {tempArray[p++] = array[p1++];}//右側小集合還有剩余，依次放入大集合尾部while (p2 <= end) {tempArray[p++] = array[p2++];}//把大集合的元素復制回原數組for (int i = 0; i < tempArray.length; i++) {array[i + start] = tempArray[i];}}public static void main(String[] args) {int[] array = { 5, 8, 6, 3, 9, 2, 1, 7 };mergeSort(array, 0, array.length - 1);System.out.println(Arrays.toString(array));} }

基數排序

import java.util.Arrays;public class RadixSort {//ascii碼的取值范圍public static final int ASCII_RANGE = 128;public static String[] radixSort(String[] array, int maxLength) {//排序結果數組，用于存儲每一次按位排序的臨時結果String[] sortedArray = new String[array.length];//從個位開始比較，一直比較到最高位for (int k = maxLength - 1; k >= 0; k--) {//計數排序的過程，分成三步：//1.創建輔助排序的統計數組，并把待排序的字符對號入座，//這里為了代碼簡潔，直接使用ascii碼范圍作為數組長度int[] count = new int[ASCII_RANGE];for (int i = 0; i < array.length; i++) {int index = getCharIndex(array[i], k);count[index]++;}//2.統計數組做變形，后面的元素等于前面的元素之和for (int i = 1; i < count.length; i++) {count[i] = count[i] + count[i - 1];}//3.倒序遍歷原始數列，從統計數組找到正確位置，輸出到結果數組for (int i = array.length - 1; i >= 0; i--) {int index = getCharIndex(array[i], k);int sortedIndex = count[index] - 1;sortedArray[sortedIndex] = array[i];count[index]--;}//下一輪排序需要以上一輪的排序結果為基礎，因此把結果復制給arrayarray = sortedArray.clone();}return array;}//獲取字符串第k位字符所對應的ascii碼序號private static int getCharIndex(String str, int k) {//如果字符串長度小于k，直接返回0，相當于給不存在的位置補0if (str.length() < (k + 1)) {return 0;}return str.charAt(k);}public static void main(String[] args) {String[] array = { "qd", "abc", "qwe", "hhh", "a", "cws", "ope" };System.out.println(Arrays.toString(radixSort(array, 3)));} }

總結

以上是生活随笔為你收集整理的《漫画算法》源码整理-5 排序算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。