本文以列舉java中比較常見(jiàn)的幾種排序：冒泡排序萧豆、快速排序、插入排序赵讯、希爾排序栏赴、選擇排序蘑斧、歸并排序以及基數(shù)排序靖秩。
冒泡排序
/**
* @author fandongfeng
* @created 2020/1/9 17:08
* @description 冒泡排序
* 兩兩比較须眷，大的右移，比出最大的沟突，然后重新開(kāi)始比
*/
public class BubbleSort {
public static void main(String[] args) {
int[] arr = new int[] {5,7,2,9,4,1,0,5,7};
bubbleSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void bubbleSort(int[] arr) {
//控制共比較多少輪
for (int i = 0; i < arr.length -1; i++) {
for (int j = 0; j < arr.length-1-i; j++) {
if(arr[j]>arr[j+1]){
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
}
快速排序
/**
* @author fandongfeng
* @created 2020/1/9 17:08
* @description 快速排序
* 開(kāi)始位置花颗，結(jié)束位置，以第一個(gè)數(shù)作為標(biāo)準(zhǔn)惠拭，比標(biāo)準(zhǔn)大的放到左邊扩劝，比標(biāo)準(zhǔn)大的放到右邊，然后遞歸標(biāo)準(zhǔn)數(shù)位置左右兩邊的數(shù)組就OK了
*/
public class QuickSort {
public static void main(String[] args) {
int[] arr = new int[] {3,4,6,7,4,1,2,9,0,5,7};
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
public static void quickSort(int[] arr, int start, int end) {
if(start < end) {
//把第0個(gè)做為標(biāo)準(zhǔn)
int stard = arr[start];
//記錄需要排序的下標(biāo)
int low = start;
int high = end;
//循環(huán)找比標(biāo)準(zhǔn)數(shù)大的數(shù)
while(low<high) {
//右邊比標(biāo)準(zhǔn)大
while(low<high && stard <= arr[high]){
high--;
}
//使用右邊數(shù)字替換左邊數(shù)字
arr[low]=arr[high];
//如果左邊數(shù)字比標(biāo)準(zhǔn)數(shù)字小
while(low<high && arr[low]<=stard){
low++;
}
arr[high] = arr[low];
}
//把標(biāo)準(zhǔn)數(shù)賦給低所在的位置的元素
arr[low] = stard;
//處理所有的比標(biāo)準(zhǔn)數(shù)小的數(shù)字
quickSort(arr, start, low-1);
//處理所有的比標(biāo)準(zhǔn)數(shù)大的數(shù)字
quickSort(arr, low+1, end);
}
}
}
插入排序
/**
* @author fandongfeng
* @created 2020/1/9 20:11
* @description 插入排序
* 默認(rèn)該位置左邊都是排好序的职辅，所以只要和左邊比較
* 如果小于左邊棒呛，則此值賦給臨時(shí)變量，左邊值賦給當(dāng)前（左邊位置+1）域携，繼續(xù)向左與臨時(shí)變量比較簇秒，小于繼續(xù)賦值給該位置+1處，
* 不滿(mǎn)足則將臨時(shí)變量賦給不滿(mǎn)足位置+1處
*/
public class InsertSort {
public static void main(String[] args) {
int[] arr = new int[] {3,4,6,7,4,1,2,9,0,5,7};
insertSort(arr);
System.out.println(Arrays.toString(arr));
}
private static void insertSort(int[] arr) {
//遍歷所有數(shù)字
for (int i = 1; i < arr.length; i++) {
//如果當(dāng)前數(shù)字比前一個(gè)小
if(arr[i] < arr[i-1]){
int temp = arr[i];
//遍歷當(dāng)前數(shù)字前面的所有數(shù)字
int j;
for (j = i-1; j >=0 && temp < arr[j]; j--) {
//把前一個(gè)數(shù)字賦給后一個(gè)數(shù)字
arr[j+1] = arr[j];
}
//把臨時(shí)變量賦給不滿(mǎn)足條件的后一個(gè)元素
arr[j+1] = temp;
}
}
}
}
希爾排序
/**
* @author fandongfeng
* @created 2020/1/9 20:41
* @description 希爾排序
* 長(zhǎng)度/2 相隔相同步長(zhǎng)的元素進(jìn)行插入排序 長(zhǎng)度/2/2 依次進(jìn)行
* 優(yōu)點(diǎn)秀鞭，將比較小的元素快速排到前面
*/
public class ShellSort {
public static void main(String[] args) {
int[] arr = new int[] {3,4,6,7,4,1,2,9,0,5,7};
shellSort(arr);
System.out.println(Arrays.toString(arr));
}
private static void shellSort(int[] arr) {
//遍歷所有步長(zhǎng)
for (int d = arr.length/2; d > 0; d/=2) {
//遍歷所有元素
for (int i = d; i < arr.length; i++) {
//遍歷本組中所有元素
for (int j = i-d; j >= 0; j-=d) {
//如果當(dāng)前元素大于加上步長(zhǎng)后的那個(gè)元素
if(arr[j] > arr[j+d]){
int temp = arr[j];
arr[j] = arr[j+d];
arr[j+d] = temp;
}
}
}
}
}
}
選擇排序
/**
* @author fandongfeng
* @created 2020/1/13 15:21
* @description 選擇排序
* 遍歷找出最小元素放在第一位趋观，遍歷找第二個(gè)...
*/
public class SelectSort {
public static void main(String[] args) {
int[] arr = new int[] {3,4,6,7,4,1,2,9,0,5,7};
selectSort(arr);
System.out.println(Arrays.toString(arr));
}
private static void selectSort(int[] arr) {
//遍歷
for (int i = 0; i < arr.length; i++) {
int minIndex = i;
//
for (int j = i+1; j < arr.length; j++) {
if(arr[minIndex] > arr[j]) {
//記錄最小坐標(biāo)
minIndex = j;
}
}
//不相等則交換
if(i != minIndex) {
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
}
歸并排序
/**
* @author fandongfeng
* @created 2020/1/13 15:43
* @description 歸并排序
* 先拆分成兩個(gè)有序數(shù)組
* 然后兩個(gè)數(shù)組合并
*/
public class MergeSort {
public static void main(String[] args) {
int[] arr = new int[] {1,3,5,2,4,6,8,10};
mergeSort(arr,0,arr.length - 1);
System.out.println(Arrays.toString(arr));
}
/**
* 將一個(gè)數(shù)組分成兩個(gè)有序數(shù)組
* 左右兩邊各遞歸出來(lái)兩個(gè)有序數(shù)組扛禽，在進(jìn)行合并
*/
public static void mergeSort(int[] arr, int low, int high) {
int middle = (low + high)/2;
if(low < high) {
//處理左邊
mergeSort(arr, low, middle);
//處理右邊
mergeSort(arr, middle+1, high);
//歸并
merge(arr, low, middle, high);
}
}
public static void merge(int[] arr, int low, int middle, int high) {
/**
* ----------arr = [1, 3, 5, 2, 4, 6, 8, 10], low = 0, middle = 0, high = 1
* ----------arr = [1, 3, 5, 2, 4, 6, 8, 10], low = 2, middle = 2, high = 3
* ----------arr = [1, 3, 2, 5, 4, 6, 8, 10], low = 0, middle = 1, high = 3
* ----------arr = [1, 2, 3, 5, 4, 6, 8, 10], low = 4, middle = 4, high = 5
* ----------arr = [1, 2, 3, 5, 4, 6, 8, 10], low = 6, middle = 6, high = 7
* ----------arr = [1, 2, 3, 5, 4, 6, 8, 10], low = 4, middle = 5, high = 7
* ----------arr = [1, 2, 3, 5, 4, 6, 8, 10], low = 0, middle = 3, high = 7
*
* [1, 2, 3, 4, 5, 6, 8, 10]
*/
System.out.println("----------arr = "+ Arrays.toString(arr)+", low = " + low + ", middle = " + middle + ", high = " + high);
//用于存儲(chǔ)歸并后的臨時(shí)數(shù)組
int[] temp = new int[high-low+1];
//記錄第一個(gè)數(shù)組中需要遍歷的下標(biāo)
int i = low;
//記錄第二個(gè)數(shù)組中需要遍歷的下標(biāo)
int j = middle + 1;
//用于記錄在臨時(shí)數(shù)組中存放的下標(biāo)
int index = 0;
//遍歷兩個(gè)數(shù)組，取出小的數(shù)字皱坛，放入臨時(shí)數(shù)組中
while (i<=middle && j<=high) {
if(arr[i] <= arr[j]) {
temp[index] = arr[i];
i++;
}else {
temp[index] = arr[j];
j++;
}
index ++;
}
//處理多余的數(shù)據(jù)
while (j <= high) {
temp[index] = arr[j];
j++;
index++;
}
while (i <= middle) {
temp[index] = arr[i];
i++;
index++;
}
//把臨時(shí)數(shù)組數(shù)據(jù)重新存入原數(shù)組
for (int k = 0; k < temp.length; k++) {
arr[k+low] = temp[k];
}
}
}
基數(shù)排序
/**
* @author fandongfeng
* @created 2020/1/13 18:57
* @description 基數(shù)排序
*/
public class RadixSort {
public static void main(String[] args) {
int[] arr = new int[]{23,6,189,45,9,287,56,1,798,34,65,652,5};
radixSort(arr);
System.out.println(Arrays.toString(arr));
}
/**
* 假設(shè)有0,1,2,3,4,5,6,7,8,9 十個(gè)桶编曼，
* 獲得最大數(shù)字位數(shù)輪詢(xún)
* 按個(gè)位數(shù)字依次放入對(duì)應(yīng)桶中，然后從0到9剩辟，先進(jìn)先出取出所有數(shù)字
* 按十位數(shù)字依次放入對(duì)應(yīng)桶中掐场，然后從0到9，先進(jìn)先出取出所有數(shù)字
* ...
* @param arr
*/
private static void radixSort(int[] arr) {
//存取數(shù)組最大數(shù)
int max = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++) {
if(arr[i] > max) {
max = arr[i];
}
}
//最大數(shù)字位數(shù)
int maxLength = (max+"").length();
//存儲(chǔ)臨時(shí)的數(shù)據(jù)數(shù)組
int[][] temp = new int[10][arr.length];
//用于記錄temp中同一列存放數(shù)字個(gè)數(shù)
int[] count = new int[10];
//根據(jù)最大長(zhǎng)度數(shù)決定比較次數(shù)
for (int i=0, n=1; i < maxLength; i++,n*=10) {
//把每一個(gè)數(shù)字分別計(jì)算余數(shù)
for (int j = 0; j < arr.length; j++) {
//余數(shù)
int ys = arr[j] / n % 10;
//存到相應(yīng)的數(shù)組中
temp[ys][count[ys]] = arr[j];
//記錄數(shù)量
count[ys]++;
}
//記錄取的元素需要放的位置
int index = 0;
//把數(shù)字取出來(lái)
for (int k = 0; k < count.length; k++) {
if(count[k] != 0) {
//循環(huán)取出元素
for (int l = 0; l < count[k]; l++) {
arr[index] = temp[k][l];
index++;
}
//把數(shù)量置為0
count[k] = 0;
}
}
}
}
}
既然是FIFO的排序抹沪，則可以用隊(duì)列代替
/**
* @author fandongfeng
* @created 2020/1/13 18:57
* @description 基數(shù)排序 - 基于隊(duì)列（FIFO）實(shí)現(xiàn)
*/
public class RadixQueueSort {
public static void main(String[] args) {
int[] arr = new int[]{23,6,189,45,9,287,56,1,798,34,65,652,5};
radixSort(arr);
System.out.println(Arrays.toString(arr));
}
/**
* 假設(shè)有0,1,2,3,4,5,6,7,8,9 十個(gè)桶刻肄，
* 獲得最大數(shù)字位數(shù)輪詢(xún)
* 按個(gè)位數(shù)字依次放入對(duì)應(yīng)桶中，然后從0到9融欧，先進(jìn)先出取出所有數(shù)字
* 按十位數(shù)字依次放入對(duì)應(yīng)桶中敏弃，然后從0到9，先進(jìn)先出取出所有數(shù)字
* ...
* @param arr
*/
private static void radixSort(int[] arr) {
//存取數(shù)組最大數(shù)
int max = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++) {
if(arr[i] > max) {
max = arr[i];
}
}
//最大數(shù)字位數(shù)
int maxLength = (max+"").length();
//存儲(chǔ)臨時(shí)的數(shù)據(jù)隊(duì)列
Queue[] temp = new LinkedBlockingQueue[10];
//初始化噪馏，防止NPE報(bào)錯(cuò)
for (int i = 0; i < temp.length; i++) {
temp[i] = new LinkedBlockingQueue();
}
//根據(jù)最大長(zhǎng)度數(shù)決定比較次數(shù)
for (int i=0, n=1; i < maxLength; i++,n*=10) {
//把每一個(gè)數(shù)字分別計(jì)算余數(shù)
for (int j = 0; j < arr.length; j++) {
//余數(shù)
int ys = arr[j] / n % 10;
//存到指定隊(duì)列
temp[ys].add(arr[j]);
}
//記錄取的元素需要放的位置
int index = 0;
//把數(shù)字取出來(lái)
for (int k = 0; k < temp.length; k++) {
if(!temp[k].isEmpty()) {
//循環(huán)取出元素
while (!temp[k].isEmpty()) {
arr[index] = Integer.valueOf(temp[k].poll()+"");
index++;
}
}
}
}
}
}
堆排序
/**
* @author fandongfeng
* @created 2020/1/14 17:58
* @description 堆排序
* 堆排序：
* 堆排序（Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法麦到。
* 堆積是一個(gè)近似完全二叉樹(shù)的結(jié)構(gòu)，并同時(shí)滿(mǎn)足堆積的性質(zhì)：
* 即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)
*
* 堆排序的基本思想是：將待排序序列構(gòu)造成一個(gè)大頂堆欠肾，
* 此時(shí)瓶颠，整個(gè)序列的最大值就是堆頂?shù)母?jié)點(diǎn)。將其與末尾元素進(jìn)行交換刺桃，此時(shí)末尾就為最大值粹淋。
* 然后將剩余n-1個(gè)元素重新構(gòu)造成一個(gè)堆，這樣會(huì)得到n個(gè)元素的次小值瑟慈。
* 如此反復(fù)執(zhí)行桃移，便能得到一個(gè)有序序列了
* 一般升序采用大頂堆，降序采用小頂堆
*/
public class HeapSort {
public static void main(String[] args) {
int[] arr = new int[] {9,6,8,7,0,1,10,4,2};
heapSort(arr);
System.out.println(Arrays.toString(arr));
}
private static void heapSort(int[] arr) {
//最后一個(gè)非葉子節(jié)點(diǎn)
int start = arr.length/2 -1;
//調(diào)整成大頂堆
for (int i = start; i >= 0; i--) {
maxHeap(arr, arr.length, i);
}
//先把數(shù)組的第0個(gè)和堆中最后一個(gè)交換位置葛碧， 在把前面的處理為大頂堆
for (int i= arr.length -1; i>0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
maxHeap(arr, i, 0);
}
}
/**
* 數(shù)組轉(zhuǎn)成大頂堆
*/
private static void maxHeap(int[] arr, int size, int index) {
//左子節(jié)點(diǎn)
int leftNode = 2*index + 1;
//右子節(jié)點(diǎn)
int rightNode = 2*index + 2;
int max = index;
//和兩個(gè)子節(jié)點(diǎn)分別對(duì)比借杰，找出最大的節(jié)點(diǎn)
if(leftNode < size && arr[leftNode] > arr[max]) {
max = leftNode;
}
if(rightNode < size && arr[rightNode] > arr[max]) {
max = rightNode;
}
//交換位置
if(max != index) {
int temp = arr[index];
arr[index] = arr[max];
arr[max] = temp;
//交換之后，可能會(huì)破壞之前排好的序
maxHeap(arr, size, max);
}
}
}
image.png
