冒泡排序
public class BubbleSort {
public static void main(String[] args) {
int[] arr =
{49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15,
35, 25, 53, 51};
bubbleSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void bubbleSort(int[] arr) {
int arrLength = arr.length;
/**
* 先以第一個數(shù)字為終點，從尾部開始，每兩個相鄰的數(shù)字相互比較默垄，如果前面的數(shù)字大于后面的數(shù)字就交換兩數(shù)病附，
* 循環(huán)結(jié)束后分唾，第一個位置上為最小的數(shù)字。
* 再以第二個數(shù)字為終點，從尾部開始，每兩個相鄰的數(shù)字相互比較榛臼，如果前面的數(shù)字大于后面的數(shù)字就交換兩數(shù)，
* 循環(huán)結(jié)束后窜司，第二個位置上為第二小的數(shù)字沛善。
* 直到以倒數(shù)第二個數(shù)字為基準，和最后一個數(shù)字比較交換完成即可塞祈。
*
* 49, 38, 65, 97, 76, 13
* 49, 38, 65, 97, 13, 76
* 49, 38, 65, 13, 97, 76
* 49, 38, 13, 65, 97, 76
* 49, 13, 38, 65, 97, 76
* 13, 49, 38, 65, 97, 76
*
* 13, 49, 38, 65, 76, 97
* 13, 38, 49, 65, 76, 97
*/
for (int i = 0; i < arrLength - 1; i++) {
for (int j = arrLength - 2; j >= i; j--) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
}
快速排序
public class QuickSort {
public static void main(String[] args) {
int[] arr =
{49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15,
35, 25, 53, 51};
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
public static void quickSort(int[] arr, int firstIndex, int lastIndex) {
/**
* 遞歸條件：當開始索引小于結(jié)束索引時金刁，否則說明兩個索引重合，即只有一個數(shù)字無需再排序
*/
if (firstIndex < lastIndex) {
/**
* 維護兩個指針议薪，頭指針初始位置為數(shù)組開始索引的位置尤蛮，尾指針初始位置為數(shù)組結(jié)束索引的位置。
* 取待排序數(shù)組的第一個數(shù)字作為基準數(shù)斯议。
*
* 如果頭指針索引等于尾指針索引抵屿，說明只有一個數(shù)字，無需進行排序捅位，
* 如果頭指針索引小于尾指針索引，說明有多個數(shù)字待排序搂抒，開始循環(huán)艇搀。
*
* 先循環(huán)操作尾指針，如果尾指針的位置在頭指針后面并且尾指針指向的數(shù)字不小于基準數(shù)求晶，
* 就將尾指針向前移動一個位置焰雕，繼續(xù)循環(huán)操作。否則說明尾指針指向的數(shù)字小于基準數(shù)或者尾指針與頭指針重合芳杏，
* 此時矩屁，將尾指針指向的數(shù)字替換頭指針指向的數(shù)字辟宗。
*
* 再循環(huán)操作頭指針，如果尾指針的位置在頭指針后面并且頭指針指向的數(shù)字不大于基準數(shù)吝秕，
* 就將頭指針向后移動一個位置泊脐，繼續(xù)循環(huán)操作。否則說明頭指針指向的數(shù)字大于基準數(shù)或者尾指針與頭指針重合烁峭，
* 此時容客，將尾指針指向的數(shù)字替換尾指針指向的數(shù)字。
*
* 如此循環(huán)约郁，直到頭指針和尾指針重合缩挑。將基準數(shù)替換當前指針（此時，頭指針和尾指針已重合）指向的數(shù)字鬓梅。
*
* 49, 38, 65, 97, 76, 13 基準數(shù)：49
* ? ?
* 13, 38, 65, 97, 76, 13
* ? ?
* 13, 38, 65, 97, 76, 13
* ? ?
* 13, 38, 65, 97, 76, 13
* ? ?
* 13, 38, 65, 97, 76, 65
* ? ?
* 13, 38, 65, 97, 76, 65
* ? ?
* 13, 38, 65, 97, 76, 65
* ? ?
* 13, 38, 65, 97, 76, 65
* ?（指針重合）
* 13, 38, 49, 97, 76, 65
*
* 此時供置，一輪操作結(jié)束后，原數(shù)組被分成兩段绽快，指針所在位置（包含）前的數(shù)字都比基準數(shù)小芥丧，
* 指針所在位置（不包含）后的數(shù)字都比基準數(shù)大。
* 對兩段數(shù)字繼續(xù)遞歸操作谎僻。
*/
int lo = firstIndex;
int hi = lastIndex;
int base = arr[lo];
while (lo < hi) {
while (arr[hi] >= base && lo < hi) {
hi--;
}
arr[lo] = arr[hi];
while (arr[lo] <= base && lo < hi) {
lo++;
}
arr[hi] = arr[lo];
}
arr[hi] = base;
quickSort(arr, firstIndex, lo);
quickSort(arr, lo + 1, lastIndex);
}
}
}
直接插入排序
public class InsertSort {
public static void main(String[] args) {
int[] arr =
{49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15,
35, 25, 53, 51};
insertSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void insertSort(int[] arr) {
int arrLength = arr.length;
for (int i = 1; i < arrLength; i++) {
int currNum = arr[i];
int j;
/**
* 要插入的數(shù)字從第二個開始娄柳，此時保證要插入的數(shù)字前面的所有數(shù)字都是已經(jīng)排好序的。
* 每個要插入的數(shù)字都和它之前的數(shù)字逐一比較艘绍，若前面的數(shù)字大于當前數(shù)字赤拒，
* 就把前面的數(shù)字向后挪一個位置，直到前面沒有數(shù)字或者前面的某一個數(shù)字小于等于當前要插入的數(shù)字為止诱鞠，
* 最后把當前要插入的數(shù)字放在對應的位置即可挎挖。
*
* 49, 38, 65, 97, 76, 13 currNum：38
* 49, 49, 65, 97, 76, 13
* 38, 49, 65, 97, 76, 13
*
* 38, 49, 65, 97, 76, 13 currNum：65
*
* 38, 49, 65, 97, 76, 13 currNum：97
*
* 38, 49, 65, 97, 76, 13 currNum：76
* 38, 49, 65, 97, 97, 13
* 38, 49, 65, 76, 97, 13
*
* 38, 49, 65, 76, 97, 13 currNum：13
* 38, 49, 65, 76, 97, 97
* 38, 49, 65, 76, 76, 97
* 38, 49, 65, 65, 76, 97
* 38, 49, 49, 65, 76, 97
* 38, 38, 49, 65, 76, 97
* 13, 38, 49, 65, 76, 97
*/
for (j = i - 1; j >= 0 && arr[j] > currNum; j--) {
arr[j + 1] = arr[j];
}
arr[j + 1] = currNum;
}
}
}
希爾排序
public class ShellSort {
public static void main(String[] args) {
int[] arr =
{49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15,
35, 25, 53, 51};
shellSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void shellSort(int[] arr) {
double distance = arr.length;
int arrLength = arr.length;
/**
* 將要排序的所有數(shù)字按增量d（n/2，n為要排序數(shù)的個數(shù)）分成若干組航夺，每組中記錄的下標相差d蕉朵，
* 對每組中全部元素進行直接插入排序，然后再用一個較小的增量（d/2）對它進行分組阳掐，在每組中再進行直接插入排序始衅。
* 當增量減到1時，最后進行一次直接插入排序即可缭保。
*
* 49, 38, 65, 97, 76, 13, 27, 49, 78 distance：4
* 49, 13, 65, 97, 76, 38, 27, 49, 78
* 49, 13, 27, 97, 76, 38, 65, 49, 78
* 49, 13, 27, 49, 76, 38, 65, 97, 78
*
* 49, 13, 27, 49, 76, 38, 65, 97, 78 distance：2
* 27, 13, 49, 38, 65, 49, 76, 97, 78
*
* 27, 13, 49, 38, 65, 49, 76, 97, 78 distance：1
* 13, 27, 38, 49, 49, 65, 76, 78, 97
*/
while (true) {
distance = Math.ceil(distance / 2);
int d = (int) distance;
for (int i = 0; i < d; i++) {
/**
* 進行直接插入排序操作
*/
for (int j = i + d; j < arrLength; j += d) {
int currNum = arr[j];
int k;
for (k = j - d; k >= 0 && arr[k] > currNum; k -= d) {
arr[k + d] = arr[k];
}
arr[k + d] = currNum;
}
}
if (d == 1) {
break;
}
}
}
}
簡單選擇排序
public class SelectSort {
public static void main(String[] args) {
int[] arr =
{49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15,
35, 25, 53, 51};
selectSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void selectSort(int[] arr) {
int arrLength = arr.length;
/**
* 從第一個數(shù)字開始汛闸，從所有數(shù)字中選擇一個最小的數(shù)字和第一個數(shù)字交換。
* 從第二個數(shù)字開始艺骂，從所有數(shù)字中選擇一個最小的數(shù)字和第二個數(shù)字交換诸老。
* 直到倒數(shù)第二個數(shù)和最后一個數(shù)字比較交換完成即可。
*
* 49, 38, 65, 97, 76, 13
*
* 13, 38, 65, 97, 76, 49
*
* 13, 38, 65, 97, 76, 49
*
* 13, 38, 49, 97, 76, 65
*
* 13, 38, 49, 65, 76, 97
*
* 13, 38, 49, 65, 76, 97
*/
for (int i = 0; i < arrLength - 1; i++) {
int min = arr[i];
int min_index = i;
for (int j = i + 1; j < arrLength; j++) {
if (arr[j] < min) {
min = arr[j];
min_index = j;
}
}
if (min_index != i) {
int temp = arr[i];
arr[i] = arr[min_index];
arr[min_index] = temp;
}
}
}
}
基數(shù)排序
public class RadixSort {
public static void main(String[] args) {
int[] arr =
{49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15,
35, 25, 53, 51};
radixSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void radixSort(int[] arr) {
/**
* 準備10個隊列钳恕，序號分別為0-9别伏。
* 先根據(jù)數(shù)組中所有數(shù)字的個位將數(shù)字放到對應的隊列中蹄衷，個位是幾，就放到幾號隊列中厘肮。
* 所有數(shù)字都放入隊列中后愧口，將所有隊列中的數(shù)字按照隊列的序號依次取出。
* 再根據(jù)數(shù)組中所有數(shù)字的十位將數(shù)字放到對應的隊列中轴脐，十位是幾调卑，就放到幾號隊列中。
* 所有數(shù)字都放入隊列中后大咱，將所有隊列中的數(shù)字按照隊列的序號依次取出恬涧。
* 再根據(jù)數(shù)組中所有數(shù)字的百位將數(shù)字放到對應的隊列中，百位是幾碴巾，就放到幾號隊列中溯捆。
* 所有數(shù)字都放入隊列中后，將所有隊列中的數(shù)字按照隊列的序號依次取出厦瓢。
* ……
*
* 49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64
*
* 隊列序號 0 1 2 3 4 5 6 7 8 9
* 12 13 34 65 76 97 38 49
* 64 27 78 49
*
* 12, 13, 34, 64, 65, 76, 97, 27, 38, 78, 49, 49
*
* 隊列序號 0 1 2 3 4 5 6 7 8 9
* 12 27 34 49 64 76 97
* 13 38 49 65 78
*
* 12, 13, 27, 34, 38, 49, 49, 64, 65, 76, 78, 97
*/
int max = arr[0];
int arrLength = arr.length;
Queue<Integer>[] queueArr = new Queue[10];
for (int i = 0; i < arrLength; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
/**
* int maxLength = (max+"").length();
*/
int maxLength = 0;
while (max > 0) {
max /= 10;
maxLength++;
}
for (int i = 0; i < 10; i++) {
queueArr[i] = new LinkedList<>();
}
for (int i = 0; i < maxLength; i++) {
for (int j = 0; j < arr.length; j++) {
int currNum = arr[j];
int num = (int) (currNum % Math.pow(10, i + 1) / Math.pow(10, i));
queueArr[num].offer(currNum);
}
int index = 0;
for (int j = 0; j < 10; j++) {
Queue<Integer> currQueue = queueArr[j];
while (!currQueue.isEmpty()) {
arr[index] = currQueue.poll();
index++;
}
}
}
}
}
歸并排序
public static void main(String[] args) {
int[] arr =
{49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15,
35, 25, 53, 51};
mergeSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
public static void mergeSort(int[] arr, int lo, int hi) {
int mid = (lo + hi) / 2;
/**
* 遞歸條件：當開始索引小于結(jié)束索引時提揍，否則說明兩個索引重合，即只有一個數(shù)字無需再遞歸
*/
if (lo < hi) {
/**
* 將數(shù)組的兩個子數(shù)組分別排序后煮仇，執(zhí)行歸并操作
*/
mergeSort(arr, lo, mid);
mergeSort(arr, mid + 1, hi);
merge(arr, lo, mid, hi);
}
}
public static void merge(int[] arr, int lo, int mid, int hi) {
/**
* 將一個數(shù)組分成兩段劳跃，可以看做是兩個子數(shù)組。新建一個臨時數(shù)組用于存放后續(xù)操作的數(shù)字浙垫。
* 維護兩個指針刨仑，分別指向兩個子數(shù)組的第一個數(shù)字。
* 比較兩個指針指向的數(shù)字夹姥，將較小的一個放入臨時數(shù)組杉武，向后移動指向較小數(shù)字的指針。
* 如此循環(huán)辙售，直到其中一個子數(shù)組中的數(shù)字都被放入臨時數(shù)組轻抱，將另一個子數(shù)組中的數(shù)字也都放入到臨時數(shù)組。
* 最后將臨時數(shù)組中的數(shù)字放回原數(shù)組中對應的位置
*
* 49, 38, 65, 76, 13, 27, 49, 78, 97 臨時數(shù)組
*
* 49, 38, 65, 97, 76, 13, 27, 49, 78
* ? ?
* 49, 38, 65, 97, 76, 13, 27, 49, 78
* ? ?
* 49, 38, 65, 97, 76, 13, 27, 49, 78
* ? ?
* 49, 38, 65, 97, 76, 13, 27, 49, 78
* ? ?
* 49, 38, 65, 97, 76, 13, 27, 49, 78
* ? ?
* 49, 38, 65, 97, 76, 13, 27, 49, 78
* ? ?
* 49, 38, 65, 97, 76, 13, 27, 49, 78
* ? ?
* 49, 38, 65, 97, 76, 13, 27, 49, 78
* ? ?
* 49, 38, 65, 97, 76, 13, 27, 49, 78
* ? ?
*/
int[] tempArr = new int[hi - lo + 1];
int index = 0;
int firstCursor = lo;
int secondCursor = mid + 1;
while (firstCursor <= mid && secondCursor <= hi) {
if (arr[firstCursor] <= arr[secondCursor]) {
tempArr[index] = arr[firstCursor];
firstCursor++;
} else {
tempArr[index] = arr[secondCursor];
secondCursor++;
}
index++;
}
while (firstCursor <= mid) {
tempArr[index] = arr[firstCursor];
firstCursor++;
index++;
}
while (secondCursor <= hi) {
tempArr[index] = arr[secondCursor];
secondCursor++;
index++;
}
for (int i = 0, tempArrLength = tempArr.length; i < tempArrLength; i++) {
arr[i + lo] = tempArr[i];
}
}
}
堆排序
public class HeapSort {
public static void main(String[] args) {
int[] arr =
{49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15,
35, 25, 53, 51};
heapSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void heapSort(int[] arr) {
/**
* 從最后一個非葉子節(jié)點開始依次向前調(diào)整二叉樹旦部，直到根節(jié)點祈搜，此時，二叉樹被調(diào)整為一個大頂堆士八。
* 最后一個葉子節(jié)點的索引為arrLength-1容燕，則最后一個非葉子節(jié)點的索引為(arrLength-1-1)/2=arrLength/2-1。
* 調(diào)整完后的大頂堆二叉樹的根節(jié)點數(shù)值（索引為0）即時最大值曹铃，將其與數(shù)組中最后一個值（索引為arrLength-1）交換，
* 固定數(shù)組最后一個值捧杉，將數(shù)組的剩余部分從根節(jié)點開始重新通過交換節(jié)點創(chuàng)建大頂堆陕见。
* 調(diào)整完后的大頂堆二叉樹的根節(jié)點數(shù)值（索引為0）即時最大值秘血，將其與數(shù)組中倒數(shù)第二個值（索引為arrLength-2）交換，
* 依次循環(huán)直到數(shù)組第一個元素评甜。
*/
int arrLength = arr.length;
int startIndex = arrLength / 2 - 1;
for (int i = startIndex; i >= 0; i--) {
transformIntoMaxHeap(arr, arrLength, i);
}
for (int i = arrLength - 1; i > 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
transformIntoMaxHeap(arr, i, 0);
}
}
public static void transformIntoMaxHeap(int[] arr, int arrLength, int nodeIndex) {
/**
* 對于某一個非葉子結(jié)點灰粮，如果其在數(shù)組中對應的索引為nodeIndex，并且假設(shè)它的左忍坷、右子節(jié)點存在粘舟，
* 則其左子節(jié)點的索引為nodeIndex*2+1，右子節(jié)點的索引為nodeIndex*2+2佩研。
* 找到這三個節(jié)點中的最大值柑肴，通過交換節(jié)點位置，將最大值交換到雙親節(jié)點的位置旬薯。
* 若發(fā)生了節(jié)點交換晰骑，則最大值原來所在位置對應的大頂堆子樹可能被破壞，需要遞歸重新調(diào)整绊序。
*/
int leftNodeIndex = nodeIndex * 2 + 1;
int rightNodeIndex = nodeIndex * 2 + 2;
int maxValueIndex = nodeIndex;
if (leftNodeIndex < arrLength && arr[leftNodeIndex] > arr[maxValueIndex]) {
maxValueIndex = leftNodeIndex;
}
if (rightNodeIndex < arrLength && arr[rightNodeIndex] > arr[maxValueIndex]) {
maxValueIndex = rightNodeIndex;
}
if (maxValueIndex != nodeIndex) {
int temp = arr[nodeIndex];
arr[nodeIndex] = arr[maxValueIndex];
arr[maxValueIndex] = temp;
transformIntoMaxHeap(arr, arrLength, maxValueIndex);
}
}
}
計數(shù)排序
public class CountSort {
public static void main(String[] args) {
int[] arr =
{49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15,
35, 25, 53, 51};
countSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void countSort(int[] arr) {
/**
* 先確定數(shù)組中的最大值硕舆，建立一個臨時數(shù)組，臨時數(shù)組長度為最大值+1骤公。
* 遍歷數(shù)組中的所有值抚官，將臨時數(shù)組中索引等于該值的位置處的值+1。
* 循環(huán)結(jié)束后阶捆，臨時數(shù)組的某個索引處的值為多少即代表原數(shù)組中該索引值的數(shù)字有多少個凌节。
* 遍歷臨時數(shù)組，重新將數(shù)字依次放入原數(shù)組即可趁猴。
*
* 4, 6, 3, 1, 8, 7, 4, 2, 3 原數(shù)組
*
* 0, 0, 0, 0, 0, 0, 0, 0, 0 臨時數(shù)組
* 0, 0, 0, 0, 1, 0, 0, 0, 0
* 0, 0, 0, 0, 1, 0, 1, 0, 0
* 0, 0, 0, 1, 1, 0, 1, 0, 0
* 0, 1, 0, 1, 1, 0, 1, 0, 0
* 0, 1, 0, 1, 1, 0, 1, 0, 1
* 0, 1, 0, 1, 1, 0, 1, 1, 1
* 0, 1, 0, 1, 2, 0, 1, 1, 1
* 0, 1, 1, 1, 2, 0, 1, 1, 1
* 0, 1, 1, 2, 2, 0, 1, 1, 1
*
* 1, 2, 3, 3, 4, 4, 6, 7, 8
*/
int max = arr[0];
for (int value : arr) {
max = value > max ? value : max;
}
int[] countArray = new int[max + 1];
for (int value : arr) {
countArray[value]++;
}
int index = 0;
for (int i = 0; i < max + 1; i++) {
for (int j = 0; j < countArray[i]; j++) {
arr[index] = i;
index++;
}
}
}
}
桶排序
public class BucketSort {
public static void main(String[] args) {
int[] arr =
{49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15,
35, 25, 53, 51};
bucketSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void bucketSort(int[] arr) {
/**
* 根據(jù)某個映射規(guī)則刊咳，將所有待排序的值映射到一系列的桶中，但需保證后一個桶中的值必須都大于前一個桶中的所有值儡司。
* 例如：值除以10后娱挨，結(jié)果的整數(shù)部分是幾就放入幾號桶中。
* 所有數(shù)字都映射完后捕犬，對每個桶中的數(shù)字排序跷坝，可以使用JDK自帶的對集合的排序。
* 最后按照桶的順序依次將桶中的數(shù)字依次取出碉碉。
*
* 49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64
*
* 桶序號
* 0
* 1 13, 12
* 2 27
* 3 38, 34
* 4 49
* 5
* 6 65, 64
* 7 76, 78
* 8
* 9 97
*
* 桶序號
* 0
* 1 12, 13
* 2 27
* 3 34, 38
* 4 49
* 5
* 6 64, 65
* 7 76, 78
* 8
* 9 97
*
* 12, 13, 27, 34, 38, 49, 64, 65, 76, 78, 97
*/
int max = arr[0];
int arrLength = arr.length;
for (int i = 0; i < arrLength; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
List<Integer>[] bucketArr = new List[max / 10 + 1];
for (int i = 0; i < max / 10 + 1; i++) {
bucketArr[i] = new LinkedList<>();
}
for (int value : arr) {
bucketArr[value / 10].add(value);
}
for (List<Integer> bucket : bucketArr) {
Collections.sort(bucket);
}
int index = 0;
for (List<Integer> bucket : bucketArr) {
for (int value : bucket) {
arr[index] = value;
index++;
}
}
}
}
