排序代碼
排序代碼：
import java.util.Arrays;
import java.util.Random;
public class CSort {
private static Random random = new Random();
public static void main(String[] args) {
int[] arrays = fill(100000);
isort(arrays);
shellsort(arrays);
mergeSort(arrays);
quickSort(arrays);
}
private static int[] fill(int number) {
int[] arrays = new int[number];
for (int i = 0; i < arrays.length; i++) {
arrays[i] = random.nextInt(number);
}
return arrays;
}
/**
* 插入排序
*
* @param arraysO arrays
*/
private static void isort(int[] arraysO) {
int[] arrays = Arrays.copyOf(arraysO, arraysO.length);
Long beginTime = System.currentTimeMillis();
for (int i = 0; i < arrays.length; i++) {
int tmp = arrays[i];
int j = i - 1;
boolean isChange = false;
while (j >= 0 && arrays[j] > tmp) {
arrays[j + 1] = arrays[j];
j--;
isChange = true;
}
if (isChange) {
arrays[j + 1] = tmp;
}
}
System.out.println("isort time " + (System.currentTimeMillis() - beginTime) * 1.0 / 1000);
// System.out.println("isort result " + Arrays.toString(arrays));
}
/**
* 希爾排序 遞增數(shù)列為n方(n2)
*
* @param arraysO arrays
*/
private static void shellsort(int[] arraysO){
int[] arrays = Arrays.copyOf(arraysO, arraysO.length);
Long beginTime = System.currentTimeMillis();
int step = arrays.length / 2;
while(step != 0){
subShellsort(arrays, step);
step = step / 2;
}
System.out.println("shell time " + (System.currentTimeMillis() - beginTime) * 1.0 / 1000);
// System.out.println("isort result " + Arrays.toString(arrays));
}
private static void subShellsort(int[] arrays, int step){
int length = arrays.length;
for (int k = 0; k < step; k++) {
for (int i = k; i < length; i+=step) {
int tmp = arrays[i];
int j = i - step;
boolean isChange = false;
while(j >= 0 && tmp < arrays[j]){
arrays[j + step] = arrays[j];
j -= step;
isChange = true;
}
if(isChange){
arrays[j + step] = tmp;
}
}
}
}
/**
* 快速排序
*
* @param arraysO arrays
*/
private static void quickSort(int[] arraysO){
int[] arrays = Arrays.copyOf(arraysO, arraysO.length);
Long beginTime = System.currentTimeMillis();
subQuicksort(arrays, 0, arrays.length - 1);
System.out.println("quick time " + (System.currentTimeMillis() - beginTime) * 1.0 / 1000);
// System.out.println("isort result " + Arrays.toString(arrays));
}
private static void subQuicksort(int[] arrays, int begin, int end){
if(begin >= end){
return;
}
int pivot = arrays[(end - begin) / 2 + 1 + begin];
int i = begin, j = end;
while(i < j){
while(arrays[i] < pivot){
i++;
}
while(arrays[j] > pivot){
j--;
}
if(i < j){
int tmp = arrays[i];
arrays[i] = arrays[j];
arrays[j] = tmp;
i++;
j--;
}
}
if(i == j){
j--;
}
subQuicksort(arrays, begin, j);
subQuicksort(arrays, i, end);
}
/**
* 歸并排序
*
* @param arraysO arrays
*/
private static void mergeSort(int[] arraysO){
int[] arrays = Arrays.copyOf(arraysO, arraysO.length);
int[] mergeArrays = new int[arrays.length];
Long beginTime = System.currentTimeMillis();
subMergeSort(arrays, mergeArrays,0, arrays.length);
System.out.println("merge time " + (System.currentTimeMillis() - beginTime) * 1.0 / 1000);
// System.out.println("isort result " + Arrays.toString(arrays));
}
private static void subMergeSort(int[] arrays, int[] mergeArrays, int begin, int end){
if(begin == end){
return;
}
int mid = (end - begin) / 2 + begin;
int begin1 = begin;
int end1 = mid;
int begin2 = mid + 1;
int end2 = end;
subMergeSort(arrays, mergeArrays, begin1, end1);
subMergeSort(arrays, mergeArrays, begin2, end2);
int k=0;
while(begin1 <= end1 && begin2 < arrays.length && begin2 <= end2){
mergeArrays[k++] = arrays[begin1] < arrays[begin2] ? arrays[begin1++] : arrays[begin2++];
}
while(begin1 <= end1 && begin1 < arrays.length){
mergeArrays[k++] = arrays[begin1++];
}
while(begin2 <= end2 && begin2 < arrays.length){
mergeArrays[k++] = arrays[begin2++];
}
for (int i = 0; i < k; i++) {
arrays[begin + i] = mergeArrays[i];
}
}
}
自測性能
簡單性能比較：
1、一萬比較
isort time 0.016
shell time 0.0
merge time 0.0
quick time 0.0
2、十萬比較
isort time 0.984
shell time 0.016
merge time 0.031
quick time 0.016
3、百萬比較：
isort time 99.128
shell time 0.18
merge time 0.2
quick time 0.099
4、千萬比較：
isort time ----
shell time 3.378
merge time 1.628
quick time 1.28
4、1億比較：
isort time ----
shell time 63.245
merge time 18.506
quick time 11.945
以上希爾排序序列均為2
快排中值均為數(shù)組中間位置值
其他
jdk中默認對對象(Object[])的排序是timeSort，它是歸并排序和插入排序的結(jié)合體，整體上是歸并排序，小范圍內(nèi)用插入排序，保證現(xiàn)實環(huán)境更快。
為什么用歸并排序而不用快速排序？
借用csdn上的話：
事實上Collections.sort方法底層就是調(diào)用的Arrays.sort方法，而Arrays.sort使用了兩種排序方法，快速排序和優(yōu)化的歸并排序。
快速排序主要是對那些基本類型數(shù)據(jù)（int,short,long等）排序， 而歸并排序用于對Object類型進行排序。
使用不同類型的排序算法主要是由于快速排序是不穩(wěn)定的，而歸并排序是穩(wěn)定的。這里的穩(wěn)定是指比較相等的數(shù)據(jù)在排序之后仍然按照排序之前的前后順序排列。對于基本數(shù)據(jù)類型，穩(wěn)定性沒有意義，而對于Object類型，穩(wěn)定性是比較重要的，因為對象相等的判斷可能只是判斷關鍵屬性，最好保持相等對象的非關鍵屬性的順序與排序前一致；另外一個原因是由于歸并排序相對而言比較次數(shù)比快速排序少，移動（對象引用的移動）次數(shù)比快速排序多，而對于對象來說，比較一般比移動耗時。
附加各種排序的時間復雜度與空間復雜度：
image
