優(yōu)化常見的java排序算法
冒泡排序
冒泡排序的思想：
每次讓當(dāng)前的元素和它的下一個元素比較大小、如果前一個的元素大于后一個元素的話，交換兩個元素。
這樣的話經(jīng)歷一次掃描之后能確保數(shù)組的最后一個元素一定是數(shù)組中最大的元素。
那么下次掃描的長度比上次少一個、因為數(shù)組的最后一個元素已經(jīng)是最大的了、即最后一個元素已經(jīng)有序了。
優(yōu)化一: 優(yōu)化的思路就是每一次掃描遍歷一次數(shù)組、如果某次的掃描之后沒有發(fā)生數(shù)組元素的交換的話、那么說明數(shù)組的元素已經(jīng)是有序的了，就可以直接跳出循環(huán)、沒有繼續(xù)掃描的必要了。
優(yōu)化二：如果數(shù)組的尾部已經(jīng)局部有序的話、那么在經(jīng)歷一次掃描之后的話、就不需要在對尾部局部有序的部分進(jìn)行掃描了。具體的做法就是記錄上一次交換的位置，然后讓下一次的掃描到上一次的記錄的位置就好了、因為記錄的位置后的元素已經(jīng)有序了。
原始的寫法
//常規(guī)的寫法
public static void bubbleSort1(int[] array) {
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array.length - i - 1; j++) {
if (array[j] > array[j + 1]) {
int tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
}
}
}
}
優(yōu)化一
//優(yōu)化一
public static void bubbleSort2(int[] array) {
boolean flag = true;
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array.length - i - 1; j++) {
if (array[j] > array[j + 1]) {
int tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
flag = false;
}
}
if (flag)
break;
}
}
優(yōu)化二
//優(yōu)化二
public static void bubbleSort3(int[] array) {
int end = array.length-1;
for (int i = end; i > 0 ; i--) {
int lastIndex = 1;
for (int j = 0; j < end; j++) {
if (array[j] > array[j + 1]) {
int tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
lastIndex = j + 1;
}
}
end = lastIndex;
}
}
選擇排序
選擇排序的思想也是類似與冒泡排序的思想。再一次掃描之后找打數(shù)組當(dāng)中最大的元素、將最大的元素放在數(shù)組的末尾。第二次的掃描數(shù)組的時候比上次掃描的長度減一
當(dāng)然也可以換種思路來實現(xiàn)選擇排序—每次掃描數(shù)組、然后找出最小的元素、將最小的元素放在數(shù)組的首位、下次掃描的時候不在掃描數(shù)組的首位、將第二小的元素放在數(shù)組第二個位置即可。
方法一
public static void selectSort1(int[] array) {
for (int end = array.length - 1; end > 0; end--) {
int maxIndex = 0;
for (int start = 0; start <= end; start++) {
if (array[maxIndex] < array[start]) {
maxIndex = start;
}
}
int tmp = array[end];
array[end] = array[maxIndex];
array[maxIndex] = tmp;
}
}
方法二
public static void selectSort2(int[] array) {
for (int start = 0; start < array.length; start++) {
int minIndex = start;
for (int end = start; end < array.length; end++) {
if (array[end] < array[minIndex]) {
minIndex = end;
}
}
int tmp = array[minIndex];
array[minIndex] = array[start];
array[start] = tmp;
}
}
堆排序
堆排可以看作是對選擇排序的一種優(yōu)化、將數(shù)組原地建成大堆、將最大的元素放在數(shù)組的最后一個位置、adjust使數(shù)組繼續(xù)保持大根堆、下一次的交換是和數(shù)組的倒數(shù)第二個元素進(jìn)行交換。思路和前面兩種排序的算法的思路一致、也是找最值、和數(shù)組的首或尾交換、下次交換的時候忽略已經(jīng)交換的元素。
當(dāng)然也可以建立一個小堆。堆頂已經(jīng)是最小的了，那么只需要比較堆頂?shù)淖蠛⒆雍陀液⒆拥拇笮〖纯?，左孩子大于右孩子的話、交換、讓右孩子adjust保持小堆（因為交換后的右孩子可能不滿足小堆）即可。
建大堆來實現(xiàn)堆排
public static void heapSort1(int[] array) {
//建大堆
for (int p = (array.length - 1 - 1) / 2; p >= 0; p--) {
adjustDown(array, p, array.length);
}
//交換
int end = array.length - 1;
while (end > 0) {
int tmp = array[0];
array[0] = array[end];
array[end] = tmp;
adjustDown(array, 0, end);
end--;
}
}
public static void adjustDown(int[] array, int p, int len) {
int child = p * 2 + 1;
while (child < len) {
if (child + 1 < len && array[child] < array[child + 1]) {
child++;
}
if (array[child] > array[p]) {
int tmp = array[child];
array[child] = array[p];
array[p] = tmp;
p = child;
child = p * 2 + 1;
} else {
break;
}
}
}
建小堆來實現(xiàn)堆排
public static void adjustDown1(int[] array, int p, int len) {
int child = p * 2 + 1;
while (child < len) {
if (child + 1 < len && array[child] > array[child + 1]) {
child++;
}
if (array[child] < array[p]) {
int tmp = array[child];
array[child] = array[p];
array[p] = tmp;
p = child;
child = p * 2 + 1;
} else {
break;
}
}
}
public static void heapSort2(int[] array) {
//建小堆
for (int p = (array.length - 1 - 1) / 2; p >= 0; p--) {
adjustDown1(array, p, array.length);
}
//交換
int startIndex = 1;
while (startIndex + 1 < array.length) {
if (array[startIndex] > array[startIndex + 1]) {
int tmp = array[startIndex];
array[startIndex] = array[startIndex + 1];
array[startIndex + 1] = tmp;
adjustDown1(array,startIndex+1,array.length);
}
startIndex++;
}
}
插入排序
插入排序的思想就是類似于打牌的時候，左手拿的排就是有序的、右手拿牌然后將牌與前面的牌進(jìn)行比較、然后插入到合適位置。
優(yōu)化一：
優(yōu)化一的思路就是將比較變?yōu)橐苿?，每次拿到元素的時候就要和前面的元素進(jìn)行比較、數(shù)組的逆序?qū)Ρ容^多的話、那么每次都要比較和交換、所以我們可以先記錄下當(dāng)前的元素的值、將該元素前面大于該元素的數(shù)字都后移一位、然后插入、這樣的話比較的和交換的次數(shù)就減少了。
優(yōu)化二:
要在前面的有序的元素中找到當(dāng)前元素要插入的位置、那么是不是可以使用二分查找來實現(xiàn)呢？所以我們可以使用二分查找來繼續(xù)優(yōu)化一下。
實現(xiàn)
public static void insertSort1(int[] array) {
for (int start = 1; start < array.length; start++) {
int cur = start;
while (cur > 0 && array[cur] < array[cur - 1]) {
int tmp = array[cur];
array[cur] = array[cur - 1];
array[cur - 1] = tmp;
cur--;
}
}
}
優(yōu)化一
public static void insertSort2(int[] array){
for (int start = 1; start < array.length; start++) {
int cur = start;
int tmp = array[start];
while (cur>0 && tmp < array[cur-1]){
array[cur] = array[cur-1];
cur--;
}
array[cur] = tmp;
}
}
優(yōu)化二
public static void insertSort3(int[] array) {
for (int start = 1; start < array.length; start++) {
int cur = array[start];
int insertIndex = searchIndex(array, start);
for (int i = start; i > insertIndex; i--) {
array[i] = array[i - 1];
}
array[insertIndex] = cur;
}
}
public static int searchIndex(int[] array, int index) {
int start = 0;
int end = index;
while (start < end) {
int mid = (start + end) >> 1;
if (array[index] < array[mid]) {
end = mid;
} else {
start = mid + 1;
}
}
return start;
}
歸并排序
歸并排序的思想就是—不斷的將當(dāng)前的序列平均分為2個子序列、直到子序列中的元素的個數(shù)為1的時候、然后不斷地將2個子序列合并成一個有序的序列。
優(yōu)化:
可以看到每次歸并的時候、申請的額外的數(shù)組的大小為左子序列的長度+右子序列的長度（end - start + 1)、歸并之后將額外的數(shù)組的值賦值到原數(shù)組的對應(yīng)的位置上。
那么我們可以做出優(yōu)化、可以直接在原數(shù)組上進(jìn)行操作、每次將左子序列的值拷貝出來、和右子序列的值比較、直接覆蓋原來的值即可。這樣每次申請的額外空間就比原來申請的空間減少一倍。
遞歸實現(xiàn)歸并排序
public static void mergerSortRec(int[] array) {
mergerRec(array, 0, array.length - 1);
}
public static void mergerRec(int[] array, int start, int end) {
if (start >= end) return;
int mid = (start + end) >> 1;
mergerRec(array, start, mid);
mergerRec(array, mid + 1, end);
merger(array, start, mid, end);
}
private static void merger(int[] array, int start, int mid, int end) {
int[] tmpArray = new int[end - start + 1];
int tmpArrayIndex = 0;
int leftStart = start;
int leftEnd = mid;
int rightStart = mid + 1;
int rightEnd = end;
while (leftStart <= leftEnd && rightStart <= rightEnd) {
if (array[leftStart] < array[rightStart]) {
tmpArray[tmpArrayIndex++] = array[leftStart++];
} else {
tmpArray[tmpArrayIndex++] = array[rightStart++];
}
}
while (leftStart <= leftEnd) {
tmpArray[tmpArrayIndex++] = array[leftStart++];
}
while (rightStart <= rightEnd) {
tmpArray[tmpArrayIndex++] = array[rightStart++];
}
for (int i = 0; i < tmpArray.length; i++) {
array[start + i] = tmpArray[i];
}
}
優(yōu)化
public static void mergerSort(int[] array, int start, int end) {
if (end - start < 2) return;
int mid = (start + end) >> 1;
mergerSort(array, start, mid);
mergerSort(array, mid, end);
merger(array, start, mid, end);
}
private static void merger(int[] array, int start, int mid, int end) {
int[] tmpLeftArray = new int[(end - start + 1) >> 1];
int ls = 0;
int le = mid - start;
int rs = mid;
int re = end;
int arrIndex = start;
for (int i = ls; i < le; i++) {
tmpLeftArray[i] = array[start + i];
}
while (ls < le) {
if (rs < re && array[rs] < tmpLeftArray[ls]) {
array[arrIndex++] = array[rs++];
} else {
array[arrIndex++] = tmpLeftArray[ls++];
}
}
}
來看O(n)的排序
public class ThreadSortDemo {
public static void main(String[] args) {
int[] array = {2, 23, 45, 5, 100, 0, 9};
for (int i = 0; i < array.length; i++) {
new ThreadSort(array[i]).start();
}
}
}
class ThreadSort extends Thread {
private int val;
ThreadSort(int val) {
this.val = val;
}
@Override
public void run() {
try {
Thread.sleep(val);
System.out.print(val + " ");
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
當(dāng)然除了基于比較的排序、還有基于非比較的排序。
計數(shù)排序：核心思想就是統(tǒng)計每個整數(shù)在序列中出現(xiàn)的次數(shù)、進(jìn)而推導(dǎo)出每個整數(shù)在有序序列中的索引。具體的做法就是先找出序列中最大的元素、開辟出最大元素+1的數(shù)組空間、統(tǒng)計每個元素出現(xiàn)的次數(shù)counts[array[i]]++、然后遍歷coutns數(shù)組、找出不為0的元素、輸出對應(yīng)的下標(biāo)即可、也可以將下標(biāo)重新放回到array數(shù)組中，也就是相當(dāng)于array數(shù)組已經(jīng)排好序了。
基數(shù)排序: 將所有元素統(tǒng)一為同樣的數(shù)位長度， 數(shù)位較短的數(shù)前面補(bǔ)零。然后， 從最低位開始， 依次進(jìn)行一次排序，這樣從最低位排序一直到最高位排序完成以后, 原數(shù)組就變成一個有序序列。
桶排序：創(chuàng)建一定數(shù)量的桶、可以使用數(shù)組或者鏈表作為桶、按照一定的規(guī)則、將序列中的元素均勻的分配到對應(yīng)的桶中、然后對每個桶中的元素進(jìn)行單獨的排序、最后將所有非空的桶的元素合并成有序序列。
總結(jié)
本篇文章就到這里了，希望對你有幫助，也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容！
相關(guān)文章
這篇文章主要介紹了Java線程實現(xiàn)的三種方式詳細(xì)解析,Java多線程實現(xiàn)方式主要有三種,繼承Thread類、實現(xiàn)Runnable接口、使用ExecutorService、Callable、Future實現(xiàn)有返回結(jié)果的多線程,需要的朋友可以參考下2023-12-12
這篇文章主要介紹了簡單了解mybatis攔截器實現(xiàn)原理及實例,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-01-01
將Java的List結(jié)構(gòu)通過GSON庫轉(zhuǎn)換為JSON的方法示例
GONS是Google在GitHub上開源的Java類庫,提供各種Java對象和JSON格式對象之間的轉(zhuǎn)換功能,將Java的List結(jié)構(gòu)通過GSON庫轉(zhuǎn)換為JSON的方法示例2016-06-06
Spring Integration 實現(xiàn)消息驅(qū)動的詳細(xì)步驟
Spring Integration是一個用于構(gòu)建消息驅(qū)動的中間件輕量級框架,它提供了一種模型和工具,用于在Spring應(yīng)用程序中實現(xiàn)企業(yè)集成模式,這篇文章主要介紹了Spring Integration 實現(xiàn)消息驅(qū)動,需要的朋友可以參考下2024-05-05
這篇文章主要介紹了Java排序算法總結(jié)之堆排序,詳細(xì)分析了堆排序的原理與java實現(xiàn)技巧,需要的朋友可以參考下2015-05-05
這篇文章主要介紹了@Scheduled 如何讀取動態(tài)配置文件的操作，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-06-06
IDEA實現(xiàn)導(dǎo)入module并成功運(yùn)行
這篇文章主要介紹了IDEA實現(xiàn)導(dǎo)入module并成功運(yùn)行方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-04-04
這篇文章主要介紹了分析java 中AspectJ切面執(zhí)行兩次的原因的相關(guān)資料,希望通過本能幫助到大家，需要的朋友可以參考下2017-09-09
java多線程事務(wù)加鎖引發(fā)bug用戶重復(fù)注冊解決分析
這篇文章主要為大家介紹了java多線程事務(wù)加鎖引發(fā)bug用戶重復(fù)注冊解決分析,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-11-11
關(guān)于Java8中map()和flatMap()的一些事
這篇文章主要給大家介紹了關(guān)于Java8中map()和flatMap()的一些事，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-10-10