Java實現(xiàn)常見的排序算法的示例代碼
更新時間:2022年10月17日 11:46:58 作者:時間郵遞員
這篇文章主要為大家詳細介紹了Java實現(xiàn)常見的排序算法(選擇排序、插入排序、希爾排序等)的相關(guān)資料,文中的示例代碼講解詳細,感興趣的可以了解一下
一、優(yōu)化后的冒泡排序
package com.yzh.sort; /* 冒泡排序 */ @SuppressWarnings({"all"}) public class BubbleSort { public static void BubbleSort(int[]a){ for (int i = 0; i <a.length-1 ; i++) { boolean flag=true; 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; flag=false; } } if(flag) break; } } }
二、選擇排序
package com.yzh.sort; @SuppressWarnings({"all"}) public class SelectSort { public static void SelectSort(int[]a) { for (int i = 0; i < a.length - 1; i++) { int index = i;//標記為待比較的數(shù) for (int j = i + 1; j < a.length; j++) { //然后從后面遍歷與第一個數(shù)比較 if (a[j] < a[index]) { //如果小,就交換最小值 index = j;//保存最小元素的下標 } } //找到最小值后,將最小的值放到第一的位置,進行下一遍循環(huán) int temp = a[index]; a[index] = a[i]; a[i] = temp; } } }
三、插入排序
package com.yzh.sort; @SuppressWarnings({"all"}) /* 插入排序 */ public class InsertSort { public static void InsertSort(int[]a){ for (int i = 0; i < a.length; i++) { //定義待插入的數(shù) int insertValue=a[i]; //找到待插入數(shù)的前一個數(shù)的下標 int insertIndex=i-1; while (insertIndex>=0 && insertValue <a[insertIndex]) {//拿a[i]前面的數(shù)比較 a[insertIndex+1]=a[insertIndex]; insertIndex--; } a[insertIndex+1]=insertValue; } } }
四、希爾排序
package com.yzh.sort; /* 希爾排序 */ @SuppressWarnings({"all"}) public class ShellSort { public static void ShellSort(int[] a){ for (int gap=a.length / 2; gap > 0; gap = gap / 2) { //將整個數(shù)組分為若干個子數(shù)組 for (int i = gap; i < a.length; i++) { //遍歷各組的元素 for (int j = i - gap; j>=0; j=j-gap) { //交換元素 if (a[j]>a[j+gap]) { int temp=a[j]; a[j]=a[j+gap]; a[j+gap]=temp; } } } } } }
五、快速排序
package com.yzh.sort; @SuppressWarnings({"all"}) /* 隨機化快速排序 */ public class QuickSort { public static void QuickSort(int[] arr,int low,int high){ int i,j,temp,t; if(low>=high){ return; } i=low; j=high; //temp就是基準位 temp = arr[low]; while (i<j) { //先看右邊,依次往左遞減 while (temp<=arr[j]&&i<j) { j--; } //再看左邊,依次往右遞增 while (temp>=arr[i]&&i<j) { i++; } //如果滿足條件則交換 if (i<j) { t = arr[j]; arr[j] = arr[i]; arr[i] = t; } } //最后將基準為與i和j相等位置的數(shù)字交換 arr[low] = arr[i]; arr[i] = temp; //遞歸調(diào)用左半數(shù)組 QuickSort(arr, low, j-1); //遞歸調(diào)用右半數(shù)組 QuickSort(arr, j+1, high); } }
六、隨機化快速排序
package com.yzh.sort; import java.util.Random; import java.util.Scanner; @SuppressWarnings({"all"}) public class RandQuickSort { public static void randsort(int[] arr, int left, int right) { if(left>=right) return; Random random = new Random(); int randIndex = random.nextInt(right-left)+left; //選取隨機主元 //把隨機主元放到數(shù)組尾部 int temp = arr[randIndex]; arr[randIndex] = arr[right]; arr[right] = temp; //數(shù)組中元素與主元比較 int i = left-1;//注意 for(int j = left;j<=right;j++) { if(arr[j]<arr[right]) { i++; int temp1 = arr[i]; arr[i] = arr[j]; arr[j] = temp1; } } //最后把主元放到適當位置 int temp2 = arr[i+1]; arr[i+1] = arr[right]; arr[right] = temp2; randsort(arr,left,i); randsort(arr,i+2,right); } }
七、歸并排序
package com.yzh.sort; @SuppressWarnings({"all"}) /* 歸并排序 */ public class MergeSort { private static void mergesort(int[] a, int left, int right, int[] temp) { //分解 if (left<right) { int mid=((right-left)>>1)+left; //向左遞歸進行分解 mergesort(a, left, mid, temp); //向右遞歸進行分解 mergesort(a, mid+1, right, temp); //每分解一次便合并一次 merge(a,left,right,mid,temp); } } private static void merge(int[] a, int left, int right, int mid, int[] temp) { int i=left; //初始i,左邊有序序列的初始索引 int j=mid+1;//初始化j,右邊有序序列的初始索引(右邊有序序列的初始位置即中間位置的后一位置) int t=0;//指向temp數(shù)組的當前索引,初始為0 //先把左右兩邊的數(shù)據(jù)(已經(jīng)有序)按規(guī)則填充到temp數(shù)組 //直到左右兩邊的有序序列,有一邊處理完成為止 while (i<=mid && j<=right) { //如果左邊有序序列的當前元素小于或等于右邊的有序序列的當前元素,就將左邊的元素填充到temp數(shù)組中 if (a[i]<=a[j]) { temp[t++]=a[i++]; }else { //反之,將右邊有序序列的當前元素填充到temp數(shù)組中 temp[t++]=a[j++]; } } //把剩余數(shù)據(jù)的一邊的元素填充到temp中 while (i<=mid) { //此時說明左邊序列還有剩余元素 //全部填充到temp數(shù)組 temp[t++]=a[i++]; } while (j<=right) { //此時說明左邊序列還有剩余元素 //全部填充到temp數(shù)組 temp[t++]=a[j++]; } //將temp數(shù)組的元素復制到原數(shù)組 t=0; int tempLeft=left; while (tempLeft<=right) { a[tempLeft++]=temp[t++]; } } }
八、可處理負數(shù)的基數(shù)排序
package com.yzh.sort; public class RadixSort{ public static void main(String[] args) { int[]a={-2,-1,-6,3,5,1,2,88,-1,99,100,21}; RadixSort(a); for (int x : a) { System.out.print(x+" "); } System.out.println(); } public static int[] RadixSort(int[] arr){ //最大值,用來計算需要找多少次 int max = Integer.MIN_VALUE; //用來判斷是否是負數(shù) int min = Integer.MAX_VALUE; //從該數(shù)組中找到最大\最小值 for (int i = 0; i < arr.length; i++) { max = Math.max(max, arr[i]); min = Math.min(min, arr[i]); } //如果最小值小于0,那么把每個數(shù)都減去最小值,這樣可以保證最小的數(shù)是0 if (min<0) { for (int i = 0; i < arr.length; i++) { arr[i] -= min; } //max也要處理 max -= min; } //計算最大值有幾位數(shù) int maxLength = (max+"").length(); //定義十個桶,每個桶就是一個一維數(shù)組 int[][] bucket = new int[10][arr.length]; //記錄每個桶中實際存放了多少個數(shù)據(jù) int[] bucketElementCount = new int[10]; //根據(jù)最大長度數(shù),決定比較次數(shù) for (int i = 0 ,n = 1 ; i < maxLength ; i++,n*=10) { //每一個數(shù)字分別計算余數(shù) for (int j = 0; j < arr.length ; j++) { int value = arr[j]/n % 10; //把當前遍歷的數(shù)放到指定的位置 bucket[value][bucketElementCount[value]] = arr[j]; //該位置加一,為下一個值進來做準備 bucketElementCount[value]++; } //記錄arr的位置 int index = 0; //遍歷取出第n次排序的值,等于0的不需要取 for (int j = 0; j < bucketElementCount.length ; j++) { if (bucketElementCount[j]!=0){ //遍歷取出數(shù)據(jù)并放到原來的arr中 for (int k = 0; k < bucketElementCount[j]; k++) { arr[index] = bucket[j][k]; index++; } } //把數(shù)量置為零,因為還有n輪 bucketElementCount[j] = 0; } } //把排序好的arr重新加上減去的值 if (min<0){ for (int i = 0; i < arr.length ; i++) { arr[i] += min; } } return arr; } }
以上就是Java實現(xiàn)常見的排序算法的示例代碼的詳細內(nèi)容,更多關(guān)于Java排序算法的資料請關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
解決shiro 定時監(jiān)聽器不生效的問題 onExpiration不調(diào)用問題
這篇文章主要介紹了解決shiro 定時監(jiān)聽器不生效的問題 onExpiration不調(diào)用問題。具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教2021-07-07Java Spring-IOC容器與Bean管理之基于注解的方式案例詳解
這篇文章主要介紹了Java Spring-IOC容器與Bean管理之基于注解的方式案例詳解,本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-08-08Java基于Swing和netty實現(xiàn)仿QQ界面聊天小項目
這篇文章主要為大家詳細介紹了Java如何利用Swing和netty實現(xiàn)仿QQ界面聊天小項目,文中的示例代碼講解詳細,感興趣的小伙伴可以了解一下2022-09-09Java中Map循環(huán)遍歷的五種方法實現(xiàn)
本文主要介紹了Java中Map循環(huán)遍歷的五種方法,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2022-07-07詳解spring cloud整合Swagger2構(gòu)建RESTful服務(wù)的APIs
這篇文章主要介紹了詳解spring cloud整合Swagger2構(gòu)建RESTful服務(wù)的APIs,小編覺得挺不錯的,現(xiàn)在分享給大家,也給大家做個參考。一起跟隨小編過來看看吧2018-01-01