溫馨提示×
您好，登錄后才能下訂單哦！
點(diǎn)擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》
您好，登錄后才能下訂單哦！
這篇文章主要介紹“java的排序算法有哪些”，在日常操作中，相信很多人在java的排序算法有哪些問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”java的排序算法有哪些”的疑惑有所幫助！接下來，請跟著小編一起來學(xué)習(xí)吧！
import java.util.Arrays;//冒泡排序public class BubbleSort_01 {
public static void main(String[] args) {
int a[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
//記錄比較次數(shù)
int count=0;
//i=0,第一輪比較
for (int i = 0; i < a.length-1; i++) {
//第一輪，兩兩比較
for (int j = 0; j < a.length-1-i; j++) {
if (a[j]>a[j+1]) {
int temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
count++;
}
}
System.out.println(Arrays.toString(a));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
System.out.println("一共比較了："+count+"次");//一共比較了：105次
}}冒泡排序的優(yōu)化1:
import java.util.Arrays;public class BubbleSort1_01 {
public static void main(String[] args) {
int a[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
int count=0;
for (int i = 0; i < a.length-1; i++) {
boolean flag=true;
for (int j = 0; j < a.length-1-i; j++) {
if (a[j]>a[j+1]) {
int temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
flag=false;
}
count++;
}
if (flag) {
break;
}
}
System.out.println(Arrays.toString(a));// [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
System.out.println("一共比較了："+count+"次");//一共比較了：95次
}}
import java.util.Arrays;//選擇排序:先定義一個(gè)記錄最小元素的下標(biāo)，然后循環(huán)一次后面的，找到最小的元素，最后將他放到前面排序好的序列。public class SelectSort_02 {
public static void main(String[] args) {
int a[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
for (int i = 0; i < a.length-1; i++) {
int index=i;//標(biāo)記第一個(gè)為待比較的數(shù)
for (int j = i+1; j < a.length; j++) { //然后從后面遍歷與第一個(gè)數(shù)比較
if (a[j]<a[index]) { //如果小,就交換最小值
index=j;//保存最小元素的下標(biāo)
}
}
//找到最小值后，將最小的值放到第一的位置，進(jìn)行下一遍循環(huán)
int temp=a[index];
a[index]=a[i];
a[i]=temp;
}
System.out.println(Arrays.toString(a));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
}}
import java.util.Arrays;//插入排序:定義一個(gè)待插入的數(shù)，再定義一個(gè)待插入數(shù)的前一個(gè)數(shù)的下標(biāo)，然后拿待插入數(shù)與前面的數(shù)組一一比較，最后交換。public class InsertSort_03 {
public static void main(String[] args) {
int a[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
for (int i = 0; i < a.length; i++) { //長度不減1，是因?yàn)橐舳嘁粋€(gè)位置方便插入數(shù)
//定義待插入的數(shù)
int insertValue=a[i];
//找到待插入數(shù)的前一個(gè)數(shù)的下標(biāo)
int insertIndex=i-1;
while (insertIndex>=0 && insertValue <a[insertIndex]) {//拿a[i]與a[i-1]的前面數(shù)組比較
a[insertIndex+1]=a[insertIndex];
insertIndex--;
}
a[insertIndex+1]=insertValue;
}
System.out.println(Arrays.toString(a));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
}}
import java.util.Arrays;//希爾排序：插入排序的升級(jí)public class ShellSort_04 {
public static void main(String[] args) {
int a[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
int count=0;//比較次數(shù)
for (int gap=a.length / 2; gap > 0; gap = gap / 2) {
//將整個(gè)數(shù)組分為若干個(gè)子數(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;
count++;
}
}
}
}
System.out.println(count);//16
System.out.println(Arrays.toString(a));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
}}參考這篇博客
import java.util.Arrays;//快速排序：冒泡排序的升華版public class QuickSort_05 {
public static void main(String[] args) {
//int a[]={50,1,12,2};
int a[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
quicksort(a,0,a.length-1);
System.out.println(Arrays.toString(a));
}
private static void quicksort(int[] a, int low, int high) {
int i,j;
if (low>high) {
return;
}
i=low;
j=high;
int temp=a[low];//基準(zhǔn)位,low=length時(shí)，會(huì)報(bào)異常，java.lang.ArrayIndexOutOfBoundsException: 4 ，所以必須在if判斷后面,就跳出方法。
while(i<j){
//先從右邊開始往左遞減，找到比temp小的值才停止
while ( temp<=a[j] && i<j) {
j--;
}
//再看左邊開始往右遞增，找到比temp大的值才停止
while ( temp>=a[i] && i<j) {
i++;
}
//滿足 i<j 就交換,繼續(xù)循環(huán)while(i<j)
if (i<j) {
int t=a[i];
a[i]=a[j];
a[j]=t;
}
}
//最后將基準(zhǔn)位跟 a[i]與a[j]相等的位置，進(jìn)行交換,此時(shí)i=j
a[low]=a[i];
a[i]=temp;
//左遞歸
quicksort(a, low, j-1);
//右遞歸
quicksort(a, j+1, high);
}}
import java.util.Arrays;//歸并排序public class MergeSort_06 {
public static void main(String[] args) {
int a[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
//int a[]={5,2,4,7,1,3,2,2};
int temp[]=new int[a.length];
mergesort(a,0,a.length-1,temp);
System.out.println(Arrays.toString(a));
}
private static void mergesort(int[] a, int left, int right, int[] temp) {
//分解
if (left<right) {
int mid=(left+right)/2;
//向左遞歸進(jìn)行分解
mergesort(a, left, mid, temp);
//向右遞歸進(jìn)行分解
mergesort(a, mid+1, right, temp);
//每分解一次便合并一次
merge(a,left,right,mid,temp);
}
}
/**
*
* @param a 待排序的數(shù)組
* @param left 左邊有序序列的初始索引
* @param right 右邊有序序列的初始索引
* @param mid 中間索引
* @param temp 做中轉(zhuǎn)的數(shù)組
*/
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ù)組的當(dāng)前索引，初始為0
//先把左右兩邊的數(shù)據(jù)（已經(jīng)有序）按規(guī)則填充到temp數(shù)組
//直到左右兩邊的有序序列，有一邊處理完成為止
while (i<=mid && j<=right) {
//如果左邊有序序列的當(dāng)前元素小于或等于右邊的有序序列的當(dāng)前元素，就將左邊的元素填充到temp數(shù)組中
if (a[i]<=a[j]) {
temp[t]=a[i];
t++;//索引向后移
i++;//i后移
}else {
//反之，將右邊有序序列的當(dāng)前元素填充到temp數(shù)組中
temp[t]=a[j];
t++;//索引向后移
j++;//j后移
}
}
//把剩余數(shù)據(jù)的一邊的元素填充到temp中
while (i<=mid) {
//此時(shí)說明左邊序列還有剩余元素
//全部填充到temp數(shù)組
temp[t]=a[i];
t++;
i++;
}
while (j<=right) {
//此時(shí)說明左邊序列還有剩余元素
//全部填充到temp數(shù)組
temp[t]=a[j];
t++;
j++;
}
//將temp數(shù)組的元素復(fù)制到原數(shù)組
t=0;
int tempLeft=left;
while (tempLeft<=right) {
a[tempLeft]=temp[t];
t++;
tempLeft++;
}
}
}堆排序
第一步：構(gòu)建初始堆buildHeap， 使用sink(arr,i, length)調(diào)整堆頂?shù)闹?
第二步：將堆頂元素下沉 目的是將最大的元素浮到堆頂來，然后使用sink(arr, 0,length)調(diào)整;
堆排序圖解：鏈接
public class Heap_Sort_07 {
public static void main(String[] args) {
int a[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
sort(a);
System.out.println(Arrays.toString(a));
}
public static void sort(int[] arr) {
int length = arr.length;
//構(gòu)建堆
buildHeap(arr,length);
for ( int i = length - 1; i > 0; i-- ) {
//將堆頂元素與末位元素調(diào)換
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
//數(shù)組長度-1 隱藏堆尾元素
length--;
//將堆頂元素下沉 目的是將最大的元素浮到堆頂來
sink(arr, 0,length);
}
}
private static void buildHeap(int[] arr, int length) {
for (int i = length / 2; i >= 0; i--) {
sink(arr,i, length);
}
}
private static void sink(int[] arr, int index, int length) {
int leftChild = 2 * index + 1;//左子節(jié)點(diǎn)下標(biāo)
int rightChild = 2 * index + 2;//右子節(jié)點(diǎn)下標(biāo)
int present = index;//要調(diào)整的節(jié)點(diǎn)下標(biāo)
//下沉左邊
if (leftChild < length && arr[leftChild] > arr[present]) {
present = leftChild;
}
//下沉右邊
if (rightChild < length && arr[rightChild] > arr[present]) {
present = rightChild;
}
//如果下標(biāo)不相等 證明調(diào)換過了
if (present != index) {
//交換值
int temp = arr[index];
arr[index] = arr[present];
arr[present] = temp;
//繼續(xù)下沉
sink(arr, present, length);
}
}}參考鏈接
算法的步驟如下：
找出待排序的數(shù)組array中最大的元素max
統(tǒng)計(jì)數(shù)組中每個(gè)值為 i 的元素出現(xiàn)的次數(shù)，存入數(shù)組 count 的第 i 項(xiàng)
對所有的計(jì)數(shù)累加（從 count中的第一個(gè)元素開始，每一項(xiàng)和前一項(xiàng)相加）
反向填充目標(biāo)數(shù)組：將每個(gè)元素 i 放在新數(shù)組的第 count [i] 項(xiàng)，每放一個(gè)元素就將 count [i] 減去
import java.util.Arrays;public class CountSort_08 {
public static void main(String[] args) {
int[] array = { 4, 2, 2, 8, 3, 3, 1 };
// 找到數(shù)組中最大的值 ---> max:8
int max = findMaxElement(array);
int[] sortedArr = countingSort(array, max + 1);
System.out.println("計(jì)數(shù)排序后的數(shù)組： " + Arrays.toString(sortedArr));
}
private static int findMaxElement(int[] array) {
int max = array[0];
for (int val : array) {
if (val > max)
max = val;
}
return max;
}
private static int[] countingSort(int[] array, int range) { //range:8+1
int[] output = new int[array.length];
int[] count = new int[range];
//初始化： count1數(shù)組
for (int i = 0; i < array.length; i++) {
count[array[i]]++;
}
//計(jì)數(shù)： count2數(shù)組，累加次數(shù)后的，這里用count2區(qū)分
for (int i = 1; i < range; i++) {
count[i] = count[i] + count[i - 1];
}
//排序：最后數(shù)組
for (int i = 0; i < array.length; i++) {
output[count[array[i]] - 1] = array[i];
count[array[i]]--;
}
return output;
}}參考鏈接
桶排序可以看成是計(jì)數(shù)排序的升級(jí)版，它將要排的數(shù)據(jù)分到多個(gè)有序的桶里，每個(gè)桶里的數(shù)據(jù)再單獨(dú)排序，再把每個(gè)桶的數(shù)據(jù)依次取出，即可完成排序。
桶排序：將值為i的元素放入i號(hào)桶，最后依次把桶里的元素倒出來。
桶排序序思路：
設(shè)置一個(gè)定量的數(shù)組當(dāng)作空桶子。
尋訪序列，并且把項(xiàng)目一個(gè)一個(gè)放到對應(yīng)的桶子去。
對每個(gè)不是空的桶子進(jìn)行排序。
從不是空的桶子里把項(xiàng)目再放回原來的序列中。
public class BucketSort_09 {
public static void sort(int[] arr){
//最大最小值
int max = arr[0];
int min = arr[0];
int length = arr.length;
for(int i=1; i<length; i++) {
if(arr[i] > max) {
max = arr[i];
} else if(arr[i] < min) {
min = arr[i];
}
}
//最大值和最小值的差
int diff = max - min;
//桶列表
ArrayList<ArrayList<Integer>> bucketList = new ArrayList<>();
for(int i = 0; i < length; i++){
bucketList.add(new ArrayList<>());
}
//每個(gè)桶的存數(shù)區(qū)間
float section = (float) diff / (float) (length - 1);
//數(shù)據(jù)入桶
for(int i = 0; i < length; i++){
//當(dāng)前數(shù)除以區(qū)間得出存放桶的位置 減1后得出桶的下標(biāo)
int num = (int) (arr[i] / section) - 1;
if(num < 0){
num = 0;
}
bucketList.get(num).add(arr[i]);
}
//桶內(nèi)排序
for(int i = 0; i < bucketList.size(); i++){
//jdk的排序速度當(dāng)然信得過
Collections.sort(bucketList.get(i));
}
//寫入原數(shù)組
int index = 0;
for(ArrayList<Integer> arrayList : bucketList){
for(int value : arrayList){
arr[index] = value;
index++;
}
}
}}我們假設(shè)有一個(gè)待排序數(shù)組[53，3，542，748，14，214]，那么如何使用基數(shù)排序?qū)ζ溥M(jìn)行排序呢？
首先我們有這樣的十個(gè)一維數(shù)組，在基數(shù)排序中也叫桶。用桶排序?qū)崿F(xiàn)。
第一輪，以元素的個(gè)位數(shù)進(jìn)行區(qū)分：[542，53，3，14，214,748]
第二輪，以元素的十位數(shù)進(jìn)行區(qū)分：[3，14，214，542，748，53]
第三輪，以元素的百位數(shù)進(jìn)行區(qū)分：[3，14，53，214，542，748]
import java.util.Arrays;public class RaixSort_10 {
public static void main(String[] args) {
int[] arr = { 53, 3, 542, 748, 14, 214 };
// 得到數(shù)組中最大的數(shù)
int max = arr[0];// 假設(shè)第一個(gè)數(shù)就是數(shù)組中的最大數(shù)
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
// 得到最大數(shù)是幾位數(shù)
// 通過拼接一個(gè)空串將其變?yōu)樽址M(jìn)而求得字符串的長度，即為位數(shù)
int maxLength = (max + "").length();
// 定義一個(gè)二維數(shù)組，模擬桶，每個(gè)桶就是一個(gè)一維數(shù)組
// 為了防止放入數(shù)據(jù)的時(shí)候桶溢出，我們應(yīng)該盡量將桶的容量設(shè)置得大一些
int[][] bucket = new int[10][arr.length];
// 記錄每個(gè)桶中實(shí)際存放的元素個(gè)數(shù)
// 定義一個(gè)一維數(shù)組來記錄每個(gè)桶中每次放入的元素個(gè)數(shù)
int[] bucketElementCounts = new int[10];
// 通過變量n幫助取出元素位數(shù)上的數(shù)
for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
for (int j = 0; j < arr.length; j++) {
// 針對每個(gè)元素的位數(shù)進(jìn)行處理
int digitOfElement = arr[j] / n % 10;
// 將元素放入對應(yīng)的桶中
// bucketElementCounts[digitOfElement]就是桶中的元素個(gè)數(shù)，初始為0，放在第一位
bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
// 將桶中的元素個(gè)數(shù)++
// 這樣接下來的元素就可以排在前面的元素后面
bucketElementCounts[digitOfElement]++;
}
// 按照桶的順序取出數(shù)據(jù)并放回原數(shù)組
int index = 0;
for (int k = 0; k < bucket.length; k++) {
// 如果桶中有數(shù)據(jù)，才取出放回原數(shù)組
if (bucketElementCounts[k] != 0) {
// 說明桶中有數(shù)據(jù)，對該桶進(jìn)行遍歷
for (int l = 0; l < bucketElementCounts[k]; l++) {
// 取出元素放回原數(shù)組
arr[index++] = bucket[k][l];
}
}
// 每輪處理后，需要將每個(gè)bucketElementCounts[k]置0
bucketElementCounts[k] = 0;
}
}
System.out.println(Arrays.toString(arr));//[3, 14, 53, 214, 542, 748]
}}基數(shù)排序是用空間換時(shí)間的經(jīng)典算法,當(dāng)數(shù)據(jù)足夠多時(shí)，達(dá)到幾千萬級(jí)別時(shí)內(nèi)存空間可能不夠用了，發(fā)生堆內(nèi)存溢出
到此，關(guān)于“java的排序算法有哪些”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請繼續(xù)關(guān)注億速云網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)砀鄬?shí)用的文章！
免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。
億速云公眾號(hào)
手機(jī)網(wǎng)站二維碼