一、冒泡排序
冒泡排序就是把小的元素往前調(diào)或者把大的元素往后調(diào)，比較是相鄰的兩個(gè)元素比較，交換也發(fā)生在這兩個(gè)元素之間。（類似于氣泡上浮過(guò)程）
動(dòng)圖演示
代碼實(shí)現(xiàn)
int a[]={2,5,3,7,4,8};
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a.length - i - 1; j++) {
if (a[j] > a[j + 1]) {
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}二、選擇排序
從未排序序列中找到最?。ㄗ畲螅旁谝雅判蛐蛄形膊?/p>
動(dòng)圖演示
代碼實(shí)現(xiàn)
int a[]={2,5,3,7,4,8};
for (int i = 0; i < a.length; i++) {
int k=i;
for (int j = i+1; j < a.length - i - 1; j++) {
if (a[j] > a[k]) {
k=j;
}
int temp = a[j];
a[j] = a[k];
a[k] = temp;
}
}三、快速排序
以一個(gè)元素為基數(shù)，將小于基數(shù)的元素移到基數(shù)前面，大于基數(shù)的元素移到基數(shù)后面，對(duì)左右區(qū)間遞歸以上步驟，直到區(qū)間只有一個(gè)數(shù)
動(dòng)圖演示
代碼實(shí)現(xiàn)
public static void quickSort(int[] a, int left, int right) {
if (left >= right) {
return;
}
int i = left;
int j = right;
int base = a[i];
while (i < j) {
//先進(jìn)行從后往前比較,比基準(zhǔn)值小的交換,否則一直往前找比基準(zhǔn)值小的
while (a[j] >= base && i < j) {
j--;
}
int temp = a[i];
a[i] = a[j];
a[j] = temp;
//再?gòu)那巴蟊容^，找比基準(zhǔn)值大的交換，否則一直往后找
while (a[i] <= base && i < j) {
i++;
}
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
//當(dāng)i=j時(shí),就以i或者j下標(biāo)的元素看成分界線,這時(shí)左邊比這個(gè)分界線的數(shù)小,右邊比這個(gè)分界線的值大。然后再對(duì)這兩個(gè)區(qū)進(jìn)行遞歸，直到每個(gè)組只剩一個(gè)數(shù)
quickSort(a, left, i - 1); //分界線左邊進(jìn)行排序
quickSort(a, i + 1, right); //分界線后邊進(jìn)行排序
}注：引用quickSort時(shí)，left為0，right為a.length-1
四、插入排序
將數(shù)組中的數(shù)據(jù)從第二位開(kāi)始向前找到合適的位置插入，有點(diǎn)類似向前的冒泡排序
動(dòng)圖演示
代碼實(shí)現(xiàn)
for (int i = 1; i < a.length; i++) {
for (int j = i; j > 0; j--) {
if (a[j]<a[j-1]){
int temp = a[j];
a[j] = a[j - 1];
a[j - 1] = temp;
} else {
break;
}
}
}五、計(jì)數(shù)排序
首先設(shè)置一個(gè)包含所有范圍數(shù)據(jù)的數(shù)組count，count[i]代表i這個(gè)數(shù)據(jù)出現(xiàn)了多少次，最后從起始位置遍歷時(shí)count[i]等于幾，就在數(shù)組中追加幾個(gè)i。計(jì)數(shù)排序是一種特殊的桶排序，適用于量大但是范圍小的數(shù)據(jù)排序，比如高考成績(jī)排名。
動(dòng)圖演示
代碼實(shí)現(xiàn)
? ? ? ? int max = a[0];
for (int i = 1; i < a.length; i++) {
if (a[i] > max) {
max = a[i];
}
}
//找出最小的數(shù)min
int min = a[0];
for (int i = 1; i < a.length; i++) {
if (a[i] < min) {
min = a[i];
}
}
//創(chuàng)建計(jì)數(shù)數(shù)組
int[] count = new int[max + 1];
//遍歷a
for (int i = 0; i < a.length; i++) {
count[a[i]]++;
}
//遍歷輸出計(jì)數(shù)數(shù)組
int k = 0;
for (int i = 0; i < count.length; i++) {
while (count[i] > 0) {
a[k++] = i; //a[k]=1; k++;
count[i]--;
}
}代碼優(yōu)化
我們考慮一個(gè)問(wèn)題，如果數(shù)組是[101,103,110,116,,119,120],如果開(kāi)辟了一個(gè)121大小的數(shù)組,前100個(gè)位置都是空的,顯然是不合適的,因此我們可以把數(shù)組的大小設(shè)置成max-min+1。這時(shí)，我們向數(shù)組中計(jì)數(shù)時(shí)，下標(biāo)要減去一個(gè)偏移量min，輸出數(shù)組的時(shí)候，要加上這個(gè)偏移量。
int max = a[0];
for (int i = 1; i < a.length; i++) {
if (a[i] > max) {
max = a[i];
}
}
//找出最小的數(shù)min
int min = a[0];
for (int i = 1; i < a.length; i++) {
if (a[i] < min) {
min = a[i];
}
}
//創(chuàng)建計(jì)數(shù)數(shù)組
int[] count = new int[max - min + 1];
//遍歷a
for (int i = 0; i < a.length; i++) {
count[a[i] - min]++;
}
//遍歷輸出計(jì)數(shù)數(shù)組
int k = 0;
for (int i = 0; i < count.length; i++) {
while (count[i] > 0) {
a[k++] =i + min; //a[k]=1; k++;
count[i]--;
}
}六、希爾排序
希爾排序可以理解成插入排序的優(yōu)化版本。
希爾排序是先將任意間隔為N的元素有序，剛開(kāi)始可以是N=n/2，接著讓N=N/2，讓N一直縮小，當(dāng)N=1,時(shí)，此時(shí)序列間隔為1有序。
動(dòng)圖演示
代碼實(shí)現(xiàn)
//希爾排序
for (int gap = a.length / 2; gap > 0; gap /= 2) {
//插入排序?qū)?換成gap
for (int i = gap; i < a.length; i++) {
for (int j = i; j - gap>=0; j -= gap) {
if (a[j] < a[j - gap]) {
int temp = a[j];
a[j] = a[j - gap];
a[j - gap] = temp;
} else {
break;
}
}
}
}七、歸并排序
歸并排序的采用分治思想，如果要排序一個(gè)數(shù)組，我們先把數(shù)組從中間分成前后兩個(gè)部分，然后對(duì)前后兩個(gè)部分分別進(jìn)行排序，再將排好序的兩部分合并在一起，這樣整個(gè)數(shù)組就都有序了。核心是merge()合并函數(shù)。
動(dòng)圖演示
代碼實(shí)現(xiàn)1（遞歸）：
public class MergeSort {
// 歸并排序(遞歸）
public static int[] mergeSort(int[] arr, int left, int right) {
// 如果 left == right，表示數(shù)組只有一個(gè)元素，則不用遞歸排序
if (left < right) {
// 把大的數(shù)組分隔成兩個(gè)數(shù)組
int mid = (left + right) / 2;
// 對(duì)左半部分進(jìn)行排序
arr = mergeSort(arr, left, mid);
// 對(duì)右半部分進(jìn)行排序
arr = mergeSort(arr, mid + 1, right);
//進(jìn)行合并
merge(arr, left, mid, right);
}
return arr;
}
// 合并函數(shù)merge，把兩個(gè)有序的數(shù)組合并起來(lái)
// arr[left..mif]表示一個(gè)數(shù)組，arr[mid+1 .. right]表示一個(gè)數(shù)組
private static void merge(int[] arr, int left, int mid, int right) {
//先用一個(gè)臨時(shí)數(shù)組把他們合并匯總起來(lái)
int[] a = new int[right - left + 1];
int i = left;
int j = mid + 1;
int k = 0;
while (i <= mid && j <= right) {
if (arr[i] < arr[j]) {
a[k++] = arr[i++];
//(即a[k]=a[i]; k=k+1; i=i+1;
} else {
a[k++] = arr[j++];
}
}
while(i <= mid) a[k++] = arr[i++];
while(j <= right) a[k++] = arr[j++];
// 把臨時(shí)數(shù)組復(fù)制到原數(shù)組
for (i = 0; i < k; i++) {
arr[left++] = a[i];
}
}
}代碼實(shí)現(xiàn)2（非遞歸）：
public class MergeSort {
// 歸并排序（非遞歸）
public static int[] mergeSort(int[] arr) {
int n = arr.length;
// 子數(shù)組的大小分別為1，2，4，8...
// 剛開(kāi)始合并的數(shù)組大小是1，接著是2，接著4....
for (int i = 1; i < n; i += i) {
//進(jìn)行數(shù)組進(jìn)行劃分
int left = 0;
int mid = left + i - 1;
int right = mid + i;
//進(jìn)行合并，對(duì)數(shù)組大小為 i 的數(shù)組進(jìn)行兩兩合并
while (right < n) {
// 合并函數(shù)和遞歸式的合并函數(shù)一樣
merge(arr, left, mid, right);
left = right + 1;
mid = left + i - 1;
right = mid + i;
}
// 還有一些被遺漏的數(shù)組沒(méi)合并，千萬(wàn)別忘了
// 因?yàn)椴豢赡苊總€(gè)字?jǐn)?shù)組的大小都剛好為 i
if (left < n && mid < n) {
merge(arr, left, mid, n - 1);
}
}
return arr;
}
}
八、桶排序
桶排序是將數(shù)組分別放到有限數(shù)量的桶里。每個(gè)桶再進(jìn)行排序。
桶排序就是把最大值和最小值之間的數(shù)進(jìn)行瓜分，例如分成 10 個(gè)區(qū)間，10個(gè)區(qū)間對(duì)應(yīng)10個(gè)桶，我們把各元素放到對(duì)應(yīng)區(qū)間的桶中去，再對(duì)每個(gè)桶中的數(shù)進(jìn)行排序，可以采用歸并排序，也可以采用快速排序之類的。
那么，桶排序當(dāng)中所謂的“桶”，又是什么概念呢？
每一個(gè)桶（bucket）代表一個(gè)區(qū)間范圍，里面可以承載一個(gè)或多個(gè)元素。桶排序的第一步，就是創(chuàng)建這些桶，確定每一個(gè)桶的區(qū)間范圍：
具體建立多少個(gè)桶，如何確定桶的區(qū)間范圍，有很多不同的方式。
我們這里創(chuàng)建的桶數(shù)量等于原始數(shù)列的元素?cái)?shù)量，除了最后一個(gè)桶只包含數(shù)列最大值，前面各個(gè)桶的區(qū)間范圍按照比例確定。
區(qū)間跨度（大?。?= （最大值-最小值）/ （桶的數(shù)量 - 1）
注：除了最后一個(gè)桶之外，其余的桶均分最大值和最小值的差值，區(qū)間跨度（大小）也就是桶的范圍的大小。
代碼中，所有的桶保存在ArrayList集合當(dāng)中，每一個(gè)桶被定義成一個(gè)鏈表（LinkedList<Double>），這樣便于在尾部插入元素。
定位元素屬于第幾個(gè)桶，是按照比例來(lái)定位：
(array[i] - min) * (bucketNum-1) / d
注：要定位元素 array[i] 在第幾個(gè)桶，先減去最小值min,看它在桶數(shù)組（ArrayList）中的偏移為多少，然后除以桶的區(qū)間大小d/(buketNum-1),相當(dāng)于乘以(buketNum-1)/d，除以桶區(qū)間大小就可以定位是在哪個(gè)桶里了。
同時(shí)，代碼使用了JDK的集合工具類Collections.sort來(lái)為桶內(nèi)部的元素進(jìn)行排序。Collections.sort底層采用的是歸并排序或Timsort，小伙伴們可以簡(jiǎn)單地把它們當(dāng)做是一種時(shí)間復(fù)雜度 O（nlogn）的排序。
動(dòng)圖演示
代碼實(shí)現(xiàn)
public static int[] BucketSort(int[] arr) {
if(arr == null || arr.length < 2) return arr;
int n = arr.length;
int max = arr[0];
int min = arr[0];
// 尋找數(shù)組的最大值與最小值
for (int i = 1; i < n; i++) {
if(min > arr[i])
min = arr[i];
if(max < arr[i])
max = arr[i];
}
//和優(yōu)化版本的計(jì)數(shù)排序一樣，弄一個(gè)大小為 min 的偏移值
int d = max - min;
//初始化桶
int bucketNum = arr.length;
ArrayList<LinkedList<Integer>> bucketList = new ArrayList<>(bucketNum);
for (int i = 0; i < bucketNum; i++) {
bucketList.add(new LinkedList<Integer>());
}
//遍歷原數(shù)組，將每個(gè)元素放入桶中
for (int i = 0; i < n; i++) {
int num = (int)((arr[i] - min) * (bucketNum - 1) / d);
bucketList.get(num).add(arr[i]);
}
//對(duì)桶內(nèi)的元素進(jìn)行排序，我這里采用系統(tǒng)自帶的排序工具
for (int i = 0; i < bucketNum; i++) {
Collections.sort(bucketList.get(i));
}
//把每個(gè)桶排序好的數(shù)據(jù)進(jìn)行合并匯總放回原數(shù)組
int k = 0;
for (int i = 0; i < bucketNum; i++) {
for (Integer t : bucketList.get(i)) {
arr[k++] = t + min;
}
}
return arr;
}ArrayList：https://www.runoob.com/java/java-arraylist.html
LinkedList：https://www.runoob.com/java/java-linkedlist.html
九、堆排序
堆的特點(diǎn)就是堆頂?shù)脑厥且粋€(gè)最值，大頂堆的堆頂是最大值，小頂堆則是最小值。
堆排序就是把堆頂?shù)脑嘏c最后一個(gè)元素交換，交換之后破壞了堆的特性，我們?cè)侔讯阎惺Ｓ嗟脑卦俅螛?gòu)成一個(gè)大頂堆，然后再把堆頂元素與最后第二個(gè)元素交換…如此往復(fù)下去，等到剩余的元素只有一個(gè)的時(shí)候，此時(shí)的數(shù)組就是有序的了。
堆（Heap）
父節(jié)點(diǎn)及子節(jié)點(diǎn)下標(biāo)的關(guān)系
動(dòng)圖演示：
思路：
1.首先將待排序的數(shù)組構(gòu)造成一個(gè)大根堆，此時(shí)，整個(gè)數(shù)組的最大值就是堆結(jié)構(gòu)的頂端
2.將頂端的數(shù)與末尾的數(shù)交換，此時(shí)，末尾的數(shù)為最大值，剩余待排序數(shù)組個(gè)數(shù)為n-1
3.將剩余的n-1個(gè)數(shù)再構(gòu)造成大根堆，再將頂端數(shù)與n-1位置的數(shù)交換，如此反復(fù)執(zhí)行，便能得到有序數(shù)組
注意:升序用大根堆，降序就用小根堆(默認(rèn)為升序)
代碼實(shí)現(xiàn)
public class Dui {
public static void main(String[] args) {
int a[]={3，1，2，5，4};
sort(a);
for (int i = 0; i < a.length; i++) {
System.out.print(a[i]+" ");
}
}
//堆排序的方法
private static void sort(int[] arr){
//建堆
for(int i = arr.length/2 - 1; i >= 0; i--){
adjustHeap(arr,i,arr.length);
}
//排序
for(int j = arr.length - 1; j > 0; j--){
//堆頂和最后一個(gè)元素交換
swap(arr,0,j);
//交換后重新建隊(duì)
adjustHeap(arr,0,j);
}
}
//建堆的方法
//實(shí)際上就是對(duì)于每一個(gè)節(jié)點(diǎn)，比較其與其子節(jié)點(diǎn)中最大的那個(gè)數(shù)，并將最大的那個(gè)數(shù)交換到節(jié)點(diǎn)位置
private static void adjustHeap(int[] arr,int i,int length){
int temp = arr[i];
for(int k = i*2+1; k < length; k = k*2+1){
if( k+1 < length && arr[k] < arr[k+1] ){//有右孩子且右孩子大于左孩子
k++;
}
if( arr[k] > temp ){//如果子大于父，則父與子節(jié)點(diǎn)交換
arr[i] = arr[k];
i = k;
}else{
break;
}
}
arr[i] = temp;
}
//交換兩個(gè)數(shù)的方法
private static void swap(int[] arr, int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}詳細(xì)內(nèi)容也可參照此博客：https://blog.csdn.net/weixin_51609435/article/details/122982075（作者Oorik）
也可參照bilibiliup主（請(qǐng)叫我AXin）的視頻https://www.bilibili.com/video/BV1fp4y1D7cj/?spm_id_from=333.337.search-card.all.click
十、基數(shù)排序
基數(shù)排序是一種特殊的桶排序
思路：先以個(gè)位數(shù)的大小來(lái)對(duì)數(shù)據(jù)進(jìn)行排序，接著以十位數(shù)的大小來(lái)多數(shù)進(jìn)行排序，接著以百位數(shù)的大小…
排到最后，就是一組有序的元素了。不過(guò)，他在以某位數(shù)進(jìn)行排序的時(shí)候，是用“桶”來(lái)排序的。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-751450.html
由于某位數(shù)（個(gè)位/十位…，不是一整個(gè)數(shù)）的大小范圍為0-9，所以我們需要10個(gè)桶，然后把具有相同數(shù)值的數(shù)放進(jìn)同一個(gè)桶里，之后再把桶里的數(shù)按照0號(hào)桶到9號(hào)桶的順序取出來(lái)，這樣一趟下來(lái)，按照某位數(shù)的排序就完成了文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-751450.html
動(dòng)圖演示
代碼實(shí)現(xiàn)
public class RadioSort {
public static int[] radioSort(int[] arr) {
if(arr == null || arr.length < 2) return arr;
int n = arr.length;
int max = arr[0];
// 找出最大值
for (int i = 1; i < n; i++) {
if(max < arr[i]) max = arr[i];
}
// 計(jì)算最大值是幾位數(shù)
int num = 1;
while (max / 10 > 0) {
num++;
max = max / 10;
}
// 創(chuàng)建10個(gè)桶
ArrayList<LinkedList<Integer>> bucketList = new ArrayList<>(10);
//初始化桶
for (int i = 0; i < 10; i++) {
bucketList.add(new LinkedList<Integer>());
}
// 進(jìn)行每一趟的排序，從個(gè)位數(shù)開(kāi)始排
for (int i = 1; i <= num; i++) {
for (int j = 0; j < n; j++) {
// 獲取每個(gè)數(shù)最后第 i 位是數(shù)組
int radio = (arr[j] / (int)Math.pow(10,i-1)) % 10;
//放進(jìn)對(duì)應(yīng)的桶里
bucketList.get(radio).add(arr[j]);
}
//合并放回原數(shù)組
int k = 0;
for (int j = 0; j < 10; j++) {
for (Integer t : bucketList.get(j)) {
arr[k++] = t;
}
//取出來(lái)合并了之后把桶清光數(shù)據(jù)
bucketList.get(j).clear();
}
}
return arr;
}
}到了這里，關(guān)于十大排序（含java代碼）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
