Java完成八個經常使用的排序算法：拔出排序、冒泡排序、選擇排序、希爾排序等。本站提示廣大學習愛好者：（Java完成八個經常使用的排序算法：拔出排序、冒泡排序、選擇排序、希爾排序等）文章只能為提供參考，不一定能成為您想要的結果。以下是Java完成八個經常使用的排序算法：拔出排序、冒泡排序、選擇排序、希爾排序等正文
本文完成了八個經常使用的排序算法：拔出排序、冒泡排序、選擇排序、希爾排序 、疾速排序、合並排序、堆排序和LST基數排序
起首是EightAlgorithms.java文件，代碼以下：
import java.util.Arrays;
/*
* 完成了八個經常使用的排序算法：拔出排序、冒泡排序、選擇排序、希爾排序
* 和疾速排序、合並排序、堆排序和LST基數排序
* @author gkh178
*/
public class EightAlgorithms {
//拔出排序：時光龐雜度o(n^2)
public static void insertSort(int a[], int n) {
for (int i = 1; i < n; ++i) {
int temp = a[i];
int j = i - 1;
while (j >= 0 && a[j] > temp) {
a[j + 1] =a[j];
--j;
}
a[j + 1] = temp;
}
}
//冒泡排序：時光龐雜度o(n^2)
public static void bubbleSort(int a[], int n) {
for (int i = n - 1; i > 0; --i) {
for (int j = 0; j < i; ++j) {
if (a[j] > a[j + 1]) {
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
}
//選擇排序：時光龐雜度o(n^2)
public static void selectSort(int a[], int n) {
for (int i = 0; i < n - 1; ++i) {
int min = a[i];
int index = i;
for (int j = i + 1; j < n; ++j) {
if (a[j] < min) {
min = a[j];
index = j;
}
}
a[index] = a[i];
a[i] = min;
}
}
//希爾排序：時光龐雜度介於o(n^2)和o(nlgn)之間
public static void shellSort(int a[], int n) {
for (int gap = n / 2; gap >= 1; gap /= 2) {
for (int i = gap; i < n; ++i) {
int temp = a[i];
int j = i -gap;
while (j >= 0 && a[j] > temp) {
a[j + gap] = a[j];
j -= gap;
}
a[j + gap] = temp;
}
}
}
//疾速排序：時光龐雜度o(nlgn)
public static void quickSort(int a[], int n) {
_quickSort(a, 0, n-1);
}
public static void _quickSort(int a[], int left, int right) {
if (left < right) {
int q = _partition(a, left, right);
_quickSort(a, left, q - 1);
_quickSort(a, q + 1, right);
}
}
public static int _partition(int a[], int left, int right) {
int pivot = a[left];
while (left < right) {
while (left < right && a[right] >= pivot) {
--right;
}
a[left] = a[right];
while (left <right && a[left] <= pivot) {
++left;
}
a[right] = a[left];
}
a[left] = pivot;
return left;
}
//合並排序：時光龐雜度o(nlgn)
public static void mergeSort(int a[], int n) {
_mergeSort(a, 0 , n-1);
}
public static void _mergeSort(int a[], int left, int right) {
if (left <right) {
int mid = left + (right - left) / 2;
_mergeSort(a, left, mid);
_mergeSort(a, mid + 1, right);
_merge(a, left, mid, right);
}
}
public static void _merge(int a[], int left, int mid, int right) {
int length = right - left + 1;
int newA[] = new int[length];
for (int i = 0, j = left; i <= length - 1; ++i, ++j) {
newA[i] = a[j];
}
int i = 0;
int j = mid -left + 1;
int k = left;
for (; i <= mid - left && j <= length - 1; ++k) {
if (newA[i] < newA[j]) {
a[k] = newA[i++];
}
else {
a[k] = newA[j++];
}
}
while (i <= mid - left) {
a[k++] = newA[i++];
}
while (j <= right - left) {
a[k++] = newA[j++];
}
}
//堆排序：時光龐雜度o(nlgn)
public static void heapSort(int a[], int n) {
builtMaxHeap(a, n);//樹立初始年夜根堆
//交流首尾元素，並對交流後消除尾元素的數組停止一次上調劑
for (int i = n - 1; i >= 1; --i) {
int temp = a[0];
a[0] = a[i];
a[i] = temp;
upAdjust(a, i);
}
}
//樹立一個長度為n的年夜根堆
public static void builtMaxHeap(int a[], int n) {
upAdjust(a, n);
}
//對長度為n的數組停止一次上調劑
public static void upAdjust(int a[], int n) {
//對每一個帶有後代節點的元素遍歷處置，從後到根節點地位
for (int i = n / 2; i >= 1; --i) {
adjustNode(a, n, i);
}
}
//調劑序號為i的節點的值
public static void adjustNode(int a[], int n, int i) {
//節點有閣下孩子
if (2 * i + 1 <= n) {
//右孩子的值年夜於節點的值，交流它們
if (a[2 * i] > a[i - 1]) {
int temp = a[2 * i];
a[2 * i] = a[i - 1];
a[i - 1] = temp;
}
//左孩子的值年夜於節點的值，交流它們
if (a[2 * i -1] > a[i - 1]) {
int temp = a[2 * i - 1];
a[2 * i - 1] = a[i - 1];
a[i - 1] = temp;
}
//對節點的閣下孩子的根節點停止調劑
adjustNode(a, n, 2 * i);
adjustNode(a, n, 2 * i + 1);
}
//節點只要左孩子，為最初一個有閣下孩子的節點
else if (2 * i == n) {
//左孩子的值年夜於節點的值，交流它們
if (a[2 * i -1] > a[i - 1]) {
int temp = a[2 * i - 1];
a[2 * i - 1] = a[i - 1];
a[i - 1] = temp;
}
}
}
//基數排序的時光龐雜度為o(distance(n+radix)),distance為位數，n為數組個數，radix為基數
//本辦法是用LST辦法停止基數排序，MST辦法不包括在內
//個中參數radix為基數，普通為10；distance表現待排序的數組的數字最長的位數；n為數組的長度
public static void lstRadixSort(int a[], int n, int radix, int distance) {
int[] newA = new int[n];//用於暫存數組
int[] count = new int[radix];//用於計數排序，保留的是以後位的值為0 到 radix-1的元素湧現的的個數
int divide = 1;
//從倒數第一名處置到第一名
for (int i = 0; i < distance; ++i) {
System.arraycopy(a, 0, newA, 0, n);//待排數組拷貝到newA數組中
Arrays.fill(count, 0);//將計數數組置0
for (int j = 0; j < n; ++j) {
int radixKey = (newA[j] / divide) % radix; //獲得數組元素確當前處置位的值
count[radixKey]++;
}
//此時count[]中每一個元素保留的是radixKey位湧現的次數
//盤算每一個radixKey在數組中的停止地位，地位序號規模為1-n
for (int j = 1; j < radix; ++j) {
count[j] = count[j] + count[j - 1];
}
//應用計數排序的道理完成一次排序，排序後的數組輸入到a[]
for (int j = n - 1; j >= 0; --j) {
int radixKey = (newA[j] / divide) % radix;
a[count[radixKey] - 1] = newA[j];
--count[radixKey];
}
divide = divide * radix;
}
}
}
然後測試代碼TestEightAlgorithms.java，代碼以下：
public class TestEightAlgorithms {
public static void printArray(int a[], int n) {
for (int i = 0; i < n; ++i) {
System.out.print(a[i] + " ");
if ( i == n - 1) {
System.out.println();
}
}
}
public static void main(String[] args) {
for (int i = 1; i <= 8; ++i) {
int arr[] = {45, 38, 26, 77, 128, 38, 25, 444, 61, 153, 9999, 1012, 43, 128};
switch(i) {
case 1:
EightAlgorithms.insertSort(arr, arr.length);
break;
case 2:
EightAlgorithms.bubbleSort(arr, arr.length);
break;
case 3:
EightAlgorithms.selectSort(arr, arr.length);
break;
case 4:
EightAlgorithms.shellSort(arr, arr.length);
break;
case 5:
EightAlgorithms.quickSort(arr, arr.length);
break;
case 6:
EightAlgorithms.mergeSort(arr, arr.length);
break;
case 7:
EightAlgorithms.heapSort(arr, arr.length);
break;
case 8:
EightAlgorithms.lstRadixSort(arr, arr.length, 10, 4);
break;
default:
break;
}
printArray(arr, arr.length);
}
}
}
最初是運轉成果以下：
以上就是Java完成八個經常使用的排序算法的全體代碼，願望年夜家對C++排序算法有更進一步的懂得。
