幾種排序實作代碼
package com.delicacy.oatmeal.test.suanfa.sort;
import java.util.Arrays;
import java.util.Random;
public class ArraySort {
public static void main(String[] args) {
int[] arr = getInts();
System.out.println("selectSort");
long a = System.nanoTime();
selectSort(arr);
long b = System.nanoTime();
System.out.println(Arrays.toString(arr));
System.out.println(b - a);
arr = getInts();
System.out.println("bubbleSort");
a = System.nanoTime();
bubbleSort(arr);
b = System.nanoTime();
System.out.println(Arrays.toString(arr));
System.out.println(b - a);
arr = getInts();
System.out.println("quickSort");
a = System.nanoTime();
quickSort(arr, 0, arr.length - 1);
b = System.nanoTime();
System.out.println(Arrays.toString(arr));
System.out.println(b - a);
arr = getInts();
System.out.println("insertSort");
a = System.nanoTime();
insertSort(arr);
b = System.nanoTime();
System.out.println(Arrays.toString(arr));
System.out.println(b - a);
arr = getInts();
System.out.println("Arrays.sort");
a = System.nanoTime();
Arrays.sort(arr);
b = System.nanoTime();
System.out.println(Arrays.toString(arr));
System.out.println(b - a);
arr = getInts();
System.out.println("shellSort");
a = System.nanoTime();
shellSort(arr);
b = System.nanoTime();
System.out.println(Arrays.toString(arr));
System.out.println(b - a);
arr = getInts();
System.out.println("mergeSort");
a = System.nanoTime();
mergeSort(arr,0,arr.length-1);
b = System.nanoTime();
System.out.println(Arrays.toString(arr));
System.out.println(b - a);
arr = getInts();
System.out.println("heapSort");
a = System.nanoTime();
heapSort(arr);
b = System.nanoTime();
System.out.println(Arrays.toString(arr));
System.out.println(b - a);
arr = getInts();
System.out.println("radixSort");
a = System.nanoTime();
radixSort(arr, 5);
b = System.nanoTime();
System.out.println(Arrays.toString(arr));
System.out.println(b - a);
}
private static int[] getInts() {
Random r = new Random();
int[] arr = new int[100];
for (int i = 0; i < arr.length; i++) {
arr[i] = r.nextInt(10000);
}
return arr;
}
/**
* 選擇排序<br/>
* <li>在未排序序列中找到最小元素，存放到排序序列的起始位置</li>
* <li>再從剩餘未排序元素中繼續尋找最小元素，然後放到排序序列末尾。</li>
* <li>以此類推，直到所有元素均排序完畢。</li>
*
* @param numbers
*/
public static void selectSort(int[] numbers) {
int tmp,size = numbers.length;
for (int i = 0; i < size; i++) {
int k = i;
for (int j = size-1; j>i; j--) {
if (numbers[j] > numbers[k]) k = j;
}
swap(numbers, i, k);
}
}
private static void swap(int[] numbers, int i, int k) {
int tmp;
tmp = numbers[i];
numbers[i] = numbers[k];
numbers[k] = tmp;
}
/**
* 冒泡法排序<br/>
* <p>
* <li>比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。</li>
* <li>對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。在這一點，最後的元素應該會是最大的數。</li>
* <li>針對所有的元素重複以上的步驟，除了最後一個。</li>
* <li>持續每次對越來越少的元素重複上面的步驟，直到沒有任何一對數字需要比較。</li>
*
* @param numbers 需要排序的整型數組
*/
public static void bubbleSort(int[] numbers) {
int tmp,size = numbers.length;
for (int i = 0; i < size - 1; i++) {
for (int j = i+1; j < size; j++) {
if (numbers[i]>numbers[j]){
swap(numbers,i,j);
}
}
}
}
/**
* 快速排序<br/>
* <ul>
* <li>從數列中挑出一個元素，稱為“基準”</li>
* <li>重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）
* 。在這個分割之後， 該基準是它的最後位置。這個稱為分割（partition）操作。</li>
* <li>遞歸地把小于基準值元素的子數列和大于基準值元素的子數列排序。</li>
* </ul>
*
* @param numbers
* @param start
* @param end
*/
public static void quickSort(int[] numbers, int start, int end) {
if(end <= start)return;
int tmp = numbers[start];
int i = start,j = end;
while (i<j){
while (i<j&&numbers[j]>=tmp)j--;
while (i<j&&numbers[i]<=tmp)i++;
if(i<j){
swap(numbers,i,j);
}
}
numbers[start] = numbers[i];
numbers[i] = tmp;
quickSort(numbers,start,i-1);
quickSort(numbers,i+1,end);
}
/**
* 插入排序
* <p>
* 從第一個元素開始，該元素可以認為已經被排序
* 取出下一個元素，在已經排序的元素序列中從後向前掃描
* 如果該元素（已排序）大于新元素，将該元素移到下一位置
* 重複步驟3，直到找到已排序的元素小于或者等于新元素的位置
* 将新元素插入到該位置中
* 重複步驟2
*
* @param numbers
*/
public static void insertSort(int[] numbers) {
int size = numbers.length,j,tmp;
for (int i = 0; i < size; i++) {
tmp = numbers[i];
for (j = i; 0 < j && numbers[j-1] <tmp ; j--) {
numbers[j] = numbers[j-1];
}
numbers[j] = tmp;
}
}
/**
* 歸并排序
* <p>
* 申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并後的序列
* 設定兩個指針，最初位置分别為兩個已經排序序列的起始位置
* 比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置
* 重複步驟3直到某一指針達到序列尾
* 将另一序列剩下的所有元素直接複制到合并序列尾
*
*/
public static void mergeSort(int a[],int start,int end){
if(a!=null&& end>start){
int mid = (end+start)/2;
mergeSort(a,start,mid);
mergeSort(a,mid+1,end);
merge(a,start,mid,end);
}
}
private static void merge(int a[], int start, int mid, int end){
int arr[] = new int[end-start+1];
int i =start,j=mid+1,k=0;
while (i<=mid && j<=end){
if (a[i]<=a[j])
arr[k++] = a[i++];
else
arr[k++] = a[j++];
}
while (i<=mid)arr[k++] = a[i++];
while (j<=end)arr[k++] = a[j++];
for (i = 0; i < k; i++) {
a[start+i] = arr[i];
}
}
/**
* 希爾排序算法
* 基本思想：先将整個待排序的記錄序列分割成為若幹子序列分别進行直接插入排序，待整個序列
* 中的記錄“基本有序”時，再對全體記錄進行依次直接插入排序
*
* @param a
*/
public static void shellSort(int[] a) {
int dk = a.length / 2;
while (dk >= 1) {
ShellInsertSort(a, dk);
dk = dk / 2;
}
}
private static void ShellInsertSort(int[] a, int dk) {
//類似插入排序，隻是插入排序增量是 1，這裡增量是 dk,把 1 換成 dk 就可以了
for (int i = dk; i < a.length; i++) {
int i1 = a[i]; // 為待插入元素
int i2 = a[i - dk];
if (i1 < i2) { // 前面的大于後面的
int j;
for (j = i - dk; j >= 0 && i1 < a[j]; j = j - dk) {
//通過循環，逐個後移一位找到要插入的位置。
a[j + dk] = a[j];
}
a[j + dk] = i1;//插入
}
}
}
/**
* 堆排序
* @param nums 待排序數組序列
* @return 排好序的數組序列
*/
public static int[] heapSort(int[] nums) {
for (int i = nums.length / 2 - 1; i >= 0; i--) {
heapAdjust(nums, i, nums.length);
}
for (int i = nums.length - 1; i > 0; i--) {
int temp = nums[i];
nums[i] = nums[0];
nums[0] = temp;
heapAdjust(nums, 0, i);
}
return nums;
}
/**
* 調整堆
*
* @param nums 待排序序列
* @param parent 待調整根節點
* @param length 數組序列長度
*/
private static void heapAdjust(int[] nums, int parent, int length) {
int temp = nums[parent];
int childIndex = 2 * parent + 1; //完全二叉樹節點i從編号1開始的左子節點位置在2i，此處數組下标從0開始，即左子節點所在數組索引位置為：2i + 1
while (childIndex < length) {
if (childIndex + 1 < length && nums[childIndex] < nums[childIndex + 1]) {
childIndex++; //節點有右子節點，且右子節點大于左子節點，則選取右子節點
}
if (temp > nums[childIndex]) {
break; //如果選中節點大于其子節點，直接傳回
}
nums[parent] = nums[childIndex];
parent = childIndex;
childIndex = 2 * parent + 1; //繼續向下調整
}
nums[parent] = temp;
}
//arr是要排序的數組，max是數組中最大的數有幾位
public static void radixSort(int[] arr, int max) {
//count數組用來計數
int[] count = new int[arr.length];
//bucket用來當桶（在下面你就了解了什麼是桶了），放資料，取資料
int[] bucket = new int[arr.length];
//k表示第幾位，1代表個位，2代表十位，3代表百位
for (int k = 1; k <= max; k++) {
//把count置空，防止上次循環的資料影響
for (int i = 0; i < arr.length; i++) {
count[i] = 0;
}
//分别統計第k位是0,1,2,3,4,5,6,7,8,9的數量
//以下便稱為桶
//即此循環用來統計每個桶中的資料的數量
for (int i = 0; i < arr.length; i++) {
count[getFigure(arr[i], k)]++;
}
//利用count[i]來确定放置資料的位置
for (int i = 1; i < arr.length; i++) {
count[i] += count[i - 1];
}
//執行完此循環之後的count[i]就是第i個桶右邊界的位置
//利用循環把資料裝入各個桶中，注意是從後往前裝
//這裡是重點，一定要仔細了解
for (int i = arr.length - 1; i >= 0; i--) {
int j = getFigure(arr[i], k);
bucket[count[j] - 1] = arr[i];
count[j]--;
}
//将桶中的資料取出來，指派給arr
for (int i = 0; i < arr.length; i++) {
arr[i] = bucket[i];
}
}
}
static int getFigure(int num, int k) {
if (k < 1) throw new IllegalArgumentException("k should not be less than 1");
return (num / pow(10,k-1)) % 10;
}
static int pow(int x, int y) {
if (y < 0) throw new IllegalArgumentException("y should not be less than 0");
int tmp = 1;
for (int i = 0; i < y; i++) {
tmp *= x;
}
return tmp;
}
}
selectSort
[9933, 9918, 9914, 9821, 9673, 9605, 9506, 9471, 9446, 9437, 9424, 9364, 9314, 9202, 9194, 8931, 8782, 8753, 8652, 8624, 8546, 8416, 8256, 8196, 8163, 8151, 8098, 7987, 7907, 7887, 7873, 7862, 7840, 7566, 7201, 6969, 6901, 6648, 6555, 6385, 6335, 6315, 6266, 6263, 6225, 6127, 6071, 6054, 5992, 5684, 5647, 5599, 5558, 5537, 5510, 5473, 5125, 5010, 4985, 4954, 4565, 4340, 4278, 4245, 4193, 4100, 3917, 3842, 3544, 3267, 3190, 3017, 2835, 2781, 2685, 2547, 2544, 2397, 2389, 2213, 2130, 2071, 2068, 1908, 1863, 1842, 1789, 1787, 1533, 1360, 971, 808, 750, 743, 736, 718, 668, 419, 308, 235]
333432
bubbleSort
[9685, 9587, 9540, 9117, 9110, 9057, 9004, 8840, 8805, 8669, 8516, 8484, 8463, 8396, 8281, 8225, 8222, 7986, 7906, 7806, 7759, 7605, 7491, 7489, 7475, 6941, 6805, 6694, 6639, 6629, 6479, 6472, 6448, 6309, 6275, 6231, 6230, 6150, 6103, 6080, 6078, 5893, 5798, 5712, 5646, 5615, 5608, 5355, 5306, 5258, 5217, 5053, 4743, 4691, 4666, 4622, 4621, 4443, 4357, 4313, 3942, 3862, 3796, 3703, 3547, 3511, 3480, 3440, 3397, 3220, 3017, 2997, 2995, 2935, 2879, 2788, 2768, 2674, 2521, 2420, 2301, 2223, 2174, 2025, 1862, 1858, 1838, 1709, 1555, 1549, 1387, 1039, 1021, 850, 742, 610, 526, 424, 249, 233]
519505
quickSort
[152, 220, 222, 254, 329, 474, 504, 982, 984, 1063, 1324, 1343, 1362, 1386, 1426, 1509, 1637, 1773, 1803, 1841, 1843, 2045, 2082, 2290, 2566, 2689, 2699, 2788, 2940, 3002, 3080, 3087, 3199, 3392, 3474, 3622, 3758, 4066, 4142, 4167, 4225, 4319, 4644, 4997, 5148, 5152, 5278, 5413, 5602, 5624, 5675, 5770, 5877, 5931, 5972, 6011, 6065, 6213, 6217, 6276, 6403, 6464, 6531, 6806, 6930, 7079, 7416, 7497, 7657, 7803, 7982, 8086, 8155, 8220, 8340, 8377, 8485, 8568, 8572, 8648, 8677, 8695, 8699, 8730, 8775, 8795, 8806, 8859, 9072, 9198, 9270, 9297, 9710, 9746, 9768, 9795, 9799, 9874, 9928, 9947]
53729
insertSort
[9935, 9891, 9857, 9669, 9326, 9181, 9098, 9074, 8984, 8941, 8926, 8715, 8693, 8518, 8204, 8074, 8065, 7972, 7969, 7913, 7841, 7840, 7722, 7591, 7534, 7506, 7456, 7292, 7253, 7102, 6867, 6571, 6546, 6516, 6451, 6427, 6319, 6131, 6016, 5956, 5863, 5820, 5818, 5807, 5536, 5368, 5314, 5279, 5219, 5126, 5124, 5079, 5036, 4895, 4669, 4661, 4611, 4509, 4355, 4341, 4174, 4154, 3961, 3942, 3748, 3545, 3289, 3140, 3013, 2913, 2903, 2800, 2766, 2766, 2744, 2685, 2666, 2662, 2555, 2482, 2398, 2226, 2183, 2131, 2113, 2105, 1966, 1949, 1929, 1746, 1577, 1369, 1238, 1154, 902, 702, 636, 407, 378, 357]
87703
Arrays.sort
[262, 367, 452, 530, 678, 725, 814, 980, 1109, 1168, 1271, 1345, 1391, 1458, 1497, 1527, 1813, 1847, 1848, 1927, 2034, 2149, 2211, 2509, 2608, 2974, 2990, 3003, 3250, 3283, 3333, 3485, 3693, 3697, 3707, 3833, 3865, 4062, 4246, 4254, 4566, 4571, 4722, 4820, 4839, 5010, 5038, 5140, 5358, 5383, 5393, 5561, 5660, 5912, 5913, 5943, 6120, 6206, 6279, 6376, 6723, 6772, 6892, 7027, 7044, 7049, 7135, 7367, 7462, 7519, 7595, 7609, 7662, 7730, 7752, 7811, 8028, 8039, 8049, 8066, 8171, 8193, 8226, 8263, 8318, 8629, 8664, 8796, 8861, 8910, 8999, 9313, 9497, 9589, 9674, 9679, 9772, 9820, 9860, 9958]
367802
mergeSort
[17, 57, 94, 241, 278, 282, 557, 581, 593, 651, 860, 908, 1168, 1201, 1696, 1707, 1795, 1961, 2380, 2381, 2386, 2570, 2589, 2599, 2622, 2629, 2677, 2701, 2748, 2756, 2810, 2862, 3039, 3073, 3839, 3844, 3844, 3915, 4040, 4154, 4386, 4404, 4628, 4742, 4848, 4876, 5262, 5514, 5742, 5779, 5800, 5811, 5865, 5881, 6010, 6222, 6226, 6297, 6467, 6674, 6819, 6959, 7077, 7131, 7147, 7298, 7351, 7381, 7504, 7542, 7584, 7676, 7700, 7738, 7828, 7875, 7929, 7968, 8062, 8104, 8225, 8300, 8351, 8409, 8934, 8965, 8972, 8989, 9039, 9084, 9214, 9326, 9460, 9481, 9562, 9667, 9820, 9837, 9839, 9851]
89283
shellSort
[9839, 9827, 9733, 9656, 9428, 9244, 9234, 9230, 9024, 8978, 8937, 8792, 8774, 8747, 8736, 8724, 8613, 8459, 8215, 8202, 8138, 7930, 7876, 7827, 7778, 7746, 7403, 7235, 6957, 6806, 6655, 6648, 6624, 6497, 6343, 6301, 6224, 6188, 6112, 6071, 5860, 5831, 5819, 5789, 5763, 5690, 5644, 5620, 5578, 5562, 5239, 5224, 5044, 5034, 4986, 4870, 4848, 4658, 4573, 4324, 4314, 3815, 3681, 3548, 3467, 3420, 3177, 3147, 3138, 3071, 2940, 2938, 2866, 2831, 2460, 2424, 2351, 2285, 2280, 2170, 2145, 2023, 1906, 1857, 1733, 1282, 1081, 981, 795, 785, 755, 498, 409, 357, 345, 326, 124, 93, 81, 62]
80197
heapSort
[91, 289, 327, 355, 583, 636, 704, 710, 810, 848, 860, 897, 946, 1122, 1180, 1234, 1258, 1358, 1393, 1667, 1690, 1773, 1779, 1906, 1919, 2008, 2018, 2055, 2123, 2135, 2212, 2580, 3109, 3724, 4162, 4309, 4440, 4469, 4675, 4721, 4869, 4948, 5029, 5037, 5065, 5185, 5357, 5490, 5535, 5548, 5615, 5635, 5750, 5780, 5785, 5874, 5934, 6094, 6238, 6271, 6301, 6309, 6337, 6458, 6530, 6550, 6581, 6618, 6625, 6640, 6683, 6742, 6946, 6960, 7006, 7013, 7017, 7036, 7108, 7424, 7435, 7551, 7573, 7651, 7707, 7883, 7927, 8246, 8521, 8567, 8651, 8752, 9190, 9210, 9212, 9425, 9608, 9709, 9907, 9935]
129976
radixSort
[105, 137, 162, 278, 314, 448, 511, 721, 769, 770, 805, 1012, 1106, 1116, 1246, 1445, 1537, 1567, 1735, 1895, 2040, 2094, 2114, 2220, 2273, 2298, 2394, 2397, 2397, 2441, 2666, 2830, 2862, 2865, 2888, 3079, 3179, 3260, 3488, 3577, 3622, 3634, 4048, 4277, 4476, 4754, 5017, 5046, 5055, 5056, 5072, 5175, 5402, 5530, 5550, 5609, 5617, 5686, 5692, 5857, 5915, 5949, 6210, 6236, 6480, 6586, 6593, 6637, 6781, 6837, 6906, 7219, 7311, 7342, 7528, 7575, 7717, 7841, 7844, 7893, 7904, 7935, 8136, 8159, 8271, 8433, 8469, 8519, 8670, 8707, 8878, 8905, 8944, 9085, 9133, 9182, 9564, 9685, 9799, 9981]
404542
一百個無規則資料排序，快排和希爾排序表現出優異的性能，而低資料量排序，則插入排序表現出優異的性能，我嘗試的是十個；可以用這些demo多做嘗試；關于原理網上有太多描述，大家自行百度。
![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)