Java完成幾種罕見排序算法代碼。本站提示廣大學習愛好者：（Java完成幾種罕見排序算法代碼）文章只能為提供參考，不一定能成為您想要的結果。以下是Java完成幾種罕見排序算法代碼正文
穩固度（穩固性）
一個排序算法是穩固的，就是當有兩個相等記載的症結字R和S，且在本來的列表中R湧現在S之前，在排序過的列表中R也將會是在S之前。
排序算法分類
罕見的有拔出（拔出排序/希爾排序）、交流（冒泡排序/疾速排序）、選擇（選擇排序）、歸並（合並排序）等。
一.拔出排序
拔出排序（Insertion Sort），它的任務道理是經由過程構建有序序列，關於未排序數據，在已排序序列中從後向前掃描，找到響應地位並拔出。拔出排序在完成上，平日采取in-place排序（即只需用到O(1)的額定空間的排序），因此在從後向前掃描進程中，須要重復把已排序元素慢慢向後挪位，為最新元素供給拔出空間。
普通來講，拔出排序都采取in-place在數組上完成。詳細算法描寫以下：
從第一個元素開端，該元素可以以為曾經被排序。
掏出下一個元素，在曾經排序的元素序列中從後向前掃描。
假如該元素（已排序）年夜於新元素，將該元素移到下一名置。
反復步調3，直到找到已排序的元素小於或許等於新元素的地位。
將新元素拔出到該地位後。
反復步調2~5。
public static void insertionSort(int[] data) {
for (int index = 1; index < data.length; index++) {
int key = data[index];
int position = index;
// shift larger values to the right
while (position > 0 && data[position - 1] > key) {
data[position] = data[position - 1];
position--;
}
data[position] = key;
}
}
二.希爾排序
希爾排序(Shell Sort)是拔出排序的一種。是針對直接拔出排序算法的改良。該辦法又稱減少增量排序，因DL．Shell於1959年提出而得名。
希爾排序是基於拔出排序的以下兩點性質而提出改良辦法的：
拔出排序在對簡直曾經排好序的數據操作時， 效力高， 便可以到達線性排序的效力。
但拔出排序普通來講是低效的， 由於拔出排序每次只能將數據挪動一名。
static <E extends Comparable<? super E>> void shellSort(List<E> a) {
int h = 1;
while (h < a.size()/3) h = h*3 + 1; // <O(n^(3/2)) by Knuth,1973>: 1, 4, 13, 40, 121, ...
for (; h >= 1; h /= 3)
for (int i = h; i < a.size(); i++)
for (int j = i; j >= h && a.get(j).compareTo(a.get(j-h)) < 0; j-=h)
Collections.swap(a, j, j-h);
}
三.冒泡排序
冒泡排序（Bubble Sort，台灣譯為：泡沫排序或氣泡排序）是一種簡略的排序算法。它反復地訪問過要排序的數列，一次比擬兩個元素，假如他們的次序毛病就把他們交流過去。訪問數列的任務是反復地停止直到沒有再須要交流，也就是說該數列曾經排序完成。這個算法的名字由來是由於越小的元素會經過交流漸漸“浮”到數列的頂端。
冒泡排序算法的運作以下：
比擬相鄰的元素，假如第一個比第二個年夜，就交流他們兩個。
對每對相鄰元素作異樣的任務，從開端第一對到開頭的最初一對，在這一點，最初的元素應當會是最年夜的數。
針對一切的元素反復以上的步調，除最初一個。
連續每次對愈來愈少的元素反復下面的步調，直到沒有任何一對數字須要比擬。
public static void bubbleSort(int[] data) {
int temp = 0;
for (int i = data.length - 1; i > 0; --i) {
boolean isSort = false;
for (int j = 0; j < i; ++j) {
if (data[j + 1] < data[j]) {
temp = data[j];
data[j] = data[j + 1];
data[j + 1] = temp;
isSort = true;
}
}
// 假如一次內輪回中產生了交流，那末持續比擬；假如一次內輪回中沒產生任何交流，則以為曾經排序好了。
if (!isSort)
break;
}
}
四.疾速排序
疾速排序（Quicksort）是對冒泡排序的一種改良。由C. A. R. Hoare在1962年提出。它的根本思惟是：經由過程一趟排序將要排序的數據朋分成自力的兩部門，個中一部門的一切數據都比別的一部門的一切數據都要小，然後再按此辦法對這兩部門數據分離停止疾速排序，全部排序進程可以遞歸停止，以此到達全部數據釀成有序序列。
疾速排序應用分治法（Divide and conquer）戰略來把一個串行（list）分為兩個子串行（sub-lists）。
步調為：
從數列中挑出一個元素，稱為 "基准"（pivot）。
從新排序數列，一切元素比基准值小的擺放在基准後面，一切元素比基准值年夜的擺在基准的前面（雷同的數可以就任一邊）。在這個分區加入以後，該基准就處於數列的中央地位。這個稱為分區（partition）操作。
遞歸地（recursive）把小於基准值元素的子數列和年夜於基准值元素的子數列排序。
/*
* more efficient implements for quicksort. <br />
* use left, center and right median value (@see #median()) for the pivot, and
* the more efficient inner loop for the core of the algorithm.
*/
public class Quicksort {
public static final int CUTOFF = 11;
/**
* quick sort algorithm. <br />
*
* @param arr an array of Comparable items. <br />
*/
public static <T extends Comparable<? super T>> void quicksort(T[] arr) {
quickSort(arr, 0, arr.length - 1);
}
/**
* get the median of the left, center and right. <br />
* order these and hide the pivot by put it the end of of the array. <br />
*
* @param arr an array of Comparable items. <br />
* @param left the most-left index of the subarray. <br />
* @param right the most-right index of the subarray.<br />
* @return T
*/
public static <T extends Comparable<? super T>> T median(T[] arr, int left, int right) {
int center = (left + right) / 2;
if (arr[left].compareTo(arr[center]) > 0)
swapRef(arr, left, center);
if (arr[left].compareTo(arr[right]) > 0)
swapRef(arr, left, right);
if (arr[center].compareTo(arr[right]) > 0)
swapRef(arr, center, right);
swapRef(arr, center, right - 1);
return arr[right - 1];
}
/**
* internal method to sort the array with quick sort algorithm. <br />
*
* @param arr an array of Comparable Items. <br />
* @param left the left-most index of the subarray. <br />
* @param right the right-most index of the subarray. <br />
*/
private static <T extends Comparable<? super T>> void quickSort(T[] arr, int left, int right) {
if (left + CUTOFF <= right) {
// find the pivot
T pivot = median(arr, left, right);
// start partitioning
int i = left, j = right - 1;
for (;;) {
while (arr[++i].compareTo(pivot) < 0);
while (arr[--j].compareTo(pivot) > 0);
if (i < j)
swapRef(arr, i, j);
else
break;
}
// swap the pivot reference back to the small collection.
swapRef(arr, i, right - 1);
quickSort(arr, left, i - 1); // sort the small collection.
quickSort(arr, i + 1, right); // sort the large collection.
} else {
// if the total number is less than CUTOFF we use insertion sort
// instead (cause it much more efficient).
insertionSort(arr, left, right);
}
}
/**
* method to swap references in an array.<br />
*
* @param arr an array of Objects. <br />
* @param idx1 the index of the first element. <br />
* @param idx2 the index of the second element. <br />
*/
public static <T> void swapRef(T[] arr, int idx1, int idx2) {
T tmp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = tmp;
}
/**
* method to sort an subarray from start to end with insertion sort
* algorithm. <br />
*
* @param arr an array of Comparable items. <br />
* @param start the begining position. <br />
* @param end the end position. <br />
*/
public static <T extends Comparable<? super T>> void insertionSort(T[] arr, int start, int end) {
int i;
for (int j = start + 1; j <= end; j++) {
T tmp = arr[j];
for (i = j; i > start && tmp.compareTo(arr[i - 1]) < 0; i--) {
arr[i] = arr[i - 1];
}
arr[i] = tmp;
}
}
private static void printArray(Integer[] c) {
for (int i = 0; i < c.length; i++)
System.out.print(c[i] + ",");
System.out.println();
}
public static void main(String[] args) {
Integer[] data = {10, 4, 9, 23, 1, 45, 27, 5, 2};
System.out.println("bubbleSort...");
printArray(data);
quicksort(data);
printArray(data);
}
}
五.選擇排序
選擇排序(Selection sort)是一種簡略直不雅的排序算法。它的任務道理以下。起首在未排序序列中找到最小（年夜）元素，寄存到排序序列的肇端地位，然後，再從殘剩未排序元素中持續尋覓最小（年夜）元素，然後放到已排序序列的末尾。以此類推，直到一切元素均排序終了。
由於每趟肯定元素的進程中都邑有一個選擇最小值的子流程，所以人們抽象地稱之為選擇排序。
舉個例子，序列5 8 5 2 9，我們曉得第一遍選擇第1個元素5會和2交流，那末原序列中2個5的絕對前後次序就被損壞了，所以選擇排序不是一個穩固的排序算法。
public static void selectSort(int[] data) {
int minIndex = 0;
int temp = 0;
for (int i = 0; i < data.length; i++) {
minIndex = i; // 無序區的最小數據數組下標
for (int j = i + 1; j < data.length; j++) { // 在無序區中找到最小數據並保留其數組下標
if (data[j] < data[minIndex]) {
minIndex = j;
}
}
if (minIndex != i) { // 假如不是無序區的最小值地位不是默許的第一個數據，則交流之。
temp = data[i];
data[i] = data[minIndex];
data[minIndex] = temp;
}
}
}
六.合並排序
合並排序（Merge sort）是樹立在合並操作上的一種有用的排序算法。該算法是采取分治法（Divide and Conquer）的一個異常典范的運用。
合並操作的進程以下：
請求空間，使其年夜小為兩個曾經排序序列之和，該空間用來寄存歸並後的序列。
設定兩個指針，最後地位分離為兩個曾經排序序列的肇端地位。
比擬兩個指針所指向的元素，選擇絕對小的元素放入到歸並空間，並挪動指針到下一名置。
反復步調3直到某一指針到達序列尾。
將另外一序列剩下的一切元素直接復制到歸並序列尾。
public static int[] mergeSort(int[] arr) {// 合並排序 --遞歸
if (arr.length == 1) {
return arr;
}
int half = arr.length / 2;
int[] arr1 = new int[half];
int[] arr2 = new int[arr.length - half];
System.arraycopy(arr, 0, arr1, 0, arr1.length);
System.arraycopy(arr, half, arr2, 0, arr2.length);
arr1 = mergeSort(arr1);
arr2 = mergeSort(arr2);
return mergeSortSub(arr1, arr2);
}
private static int[] mergeSortSub(int[] arr1, int[] arr2) {// 合並排序子法式
int[] result = new int[arr1.length + arr2.length];
int i = 0;
int j = 0;
int k = 0;
while (true) {
if (arr1[i] < arr2[j]) {
result[k] = arr1[i];
if (++i > arr1.length - 1) {
break;
}
} else {
result[k] = arr2[j];
if (++j > arr2.length - 1) {
break;
}
}
k++;
}
for (; i < arr1.length; i++) {
result[++k] = arr1[i];
}
for (; j < arr2.length; j++) {
result[++k] = arr2[j];
}
return result;
}
完全代碼（除QuickSort）
package com.clzhang.sample.thinking;
import java.util.*;
/**
* 幾路罕見的排序算法Java完成
* @author acer
*
*/
public class CommonSort {
/**
* 拔出排序詳細算法描寫以下：
* 1.從第一個元素開端，該元素可以以為曾經被排序
* 2.掏出下一個元素，在曾經排序的元素序列中從後向前掃描
* 3.假如該元素（已排序）年夜於新元素，將該元素移到下一名置
* 4.反復步調3，直到找到已排序的元素小於或許等於新元素的地位
* 5.將新元素拔出到該地位後
* 6.反復步調2~5
*/
public static void insertionSort(int[] data) {
for (int index = 1; index < data.length; index++) {
int key = data[index];
int position = index;
// shift larger values to the right
while (position > 0 && data[position - 1] > key) {
data[position] = data[position - 1];
position--;
}
data[position] = key;
}
}
/**
* 希爾排序，算法完成思惟參考維基百科；合適年夜數目排序操作。
*/
static <E extends Comparable<? super E>> void shellSort(List<E> a) {
int h = 1;
while (h < a.size()/3) h = h*3 + 1; // <O(n^(3/2)) by Knuth,1973>: 1, 4, 13, 40, 121, ...
for (; h >= 1; h /= 3)
for (int i = h; i < a.size(); i++)
for (int j = i; j >= h && a.get(j).compareTo(a.get(j-h)) < 0; j-=h)
Collections.swap(a, j, j-h);
}
/**
* 冒泡排序算法的運作以下：
* 1.比擬相鄰的元素。假如第一個比第二個年夜，就交流他們兩個。
* 2.對每對相鄰元素作異樣的任務，從開端第一對到開頭的最初一對。在這一點，最初的元素應當會是最年夜的數。
* 3.針對一切的元素反復以上的步調，除最初一個。
* 4.連續每次對愈來愈少的元素反復下面的步調，直到沒有任何一對數字須要比擬。[1]
*/
public static void bubbleSort(int[] data) {
int temp = 0;
for (int i = data.length - 1; i > 0; --i) {
boolean isSort = false;
for (int j = 0; j < i; ++j) {
if (data[j + 1] < data[j]) {
temp = data[j];
data[j] = data[j + 1];
data[j + 1] = temp;
isSort = true;
}
}
// 假如一次內輪回中產生了交流，那末持續比擬；假如一次內輪回中沒產生任何交流，則以為曾經排序好了。
if (!isSort)
break;
}
}
/**
* 選擇排序的根本思惟是：
* 1.遍歷數組的進程中，以 i 代表以後須要排序的序號，則須要在殘剩的 [i+1…n-1] 中找出個中的最小值，
* 2.然後將找到的最小值與 i 指向的值停止交流。
* 由於每趟肯定元素的進程中都邑有一個選擇最小值的子流程，所以人們抽象地稱之為選擇排序。
* @param data
*/
public static void selectSort(int[] data) {
int minIndex = 0;
int temp = 0;
for (int i = 0; i < data.length; i++) {
minIndex = i; // 無序區的最小數據數組下標
for (int j = i + 1; j < data.length; j++) { // 在無序區中找到最小數據並保留其數組下標
if (data[j] < data[minIndex]) {
minIndex = j;
}
}
if (minIndex != i) { // 假如不是無序區的最小值地位不是默許的第一個數據，則交流之。
temp = data[i];
data[i] = data[minIndex];
data[minIndex] = temp;
}
}
}
/**
* 合並操作的進程以下：
* 1.請求空間，使其年夜小為兩個曾經排序序列之和，該空間用來寄存歸並後的序列
* 2.設定兩個指針，最後地位分離為兩個曾經排序序列的肇端地位
* 3.比擬兩個指針所指向的元素，選擇絕對小的元素放入到歸並空間，並挪動指針到下一名置
* 4.反復步調3直到某一指針到達序列尾
* 5.將另外一序列剩下的一切元素直接復制到歸並序列尾
*/
public static int[] mergeSort(int[] arr) {// 合並排序 --遞歸
if (arr.length == 1) {
return arr;
}
int half = arr.length / 2;
int[] arr1 = new int[half];
int[] arr2 = new int[arr.length - half];
System.arraycopy(arr, 0, arr1, 0, arr1.length);
System.arraycopy(arr, half, arr2, 0, arr2.length);
arr1 = mergeSort(arr1);
arr2 = mergeSort(arr2);
return mergeSortSub(arr1, arr2);
}
private static int[] mergeSortSub(int[] arr1, int[] arr2) {// 合並排序子法式
int[] result = new int[arr1.length + arr2.length];
int i = 0;
int j = 0;
int k = 0;
while (true) {
if (arr1[i] < arr2[j]) {
result[k] = arr1[i];
if (++i > arr1.length - 1) {
break;
}
} else {
result[k] = arr2[j];
if (++j > arr2.length - 1) {
break;
}
}
k++;
}
for (; i < arr1.length; i++) {
result[++k] = arr1[i];
}
for (; j < arr2.length; j++) {
result[++k] = arr2[j];
}
return result;
}
private static void printArray(int[] c) {
for (int i = 0; i < c.length; i++)
System.out.print(c[i] + ",");
System.out.println();
}
public static void main(String []args){
int[] data = {10,4,9,23,1,45,27,5,2};
System.out.println("bubbleSort...");
int[] a = data.clone();
printArray(a);
bubbleSort(a);
printArray(a);
System.out.println("selectSort...");
int[] b = data.clone();
printArray(b);
selectSort(b);
printArray(b);
System.out.println("insertionSort...");
int[] c = data.clone();
printArray(c);
insertionSort(c);
printArray(c);
System.out.println("shellSort...");
List<Integer> list = new ArrayList<Integer>();
for(int i=0;i<data.length;i++)
list.add(data[i]);
System.out.println(list);
shellSort(list);
System.out.println(list);
System.out.println("mergeSort...");
int[] d = data.clone();
printArray(d);
printArray(mergeSort(d));
}
}
