7种排序的Java实现及性能对比
数据无序的情况下
数据无序的情况下
---------------------------------------------------------------
排序前arr1=[2335859, 4953324, 1557066, 3003226, 5835311, 7214849, 1675280, 2755795, 7679796, 6588744, 6037572, 1898931, 161634, 4769500, 3683284, 2155048, 5878137, 6051124, 2035316, 5968625]省略以下700w+个数据..
堆排序
堆排序800w个元素耗时2247ms
排序后arr1=[0, 0, 3, 6, 6, 7, 9, 9, 9, 11, 12, 15, 16, 17, 18, 19, 20, 21, 22, 23]省略以下700w+个数据..
---------------------------------------------------------------
排序前arr2=[2335859, 4953324, 1557066, 3003226, 5835311, 7214849, 1675280, 2755795, 7679796, 6588744, 6037572, 1898931, 161634, 4769500, 3683284, 2155048, 5878137, 6051124, 2035316, 5968625]省略以下700w+个数据..
快速排序
随机快速排序800w个元素耗时925ms
排序后arr2=[0, 0, 3, 6, 6, 7, 9, 9, 9, 11, 12, 15, 16, 17, 18, 19, 20, 21, 22, 23]省略以下700w+个数据..
---------------------------------------------------------------
排序前arr3=[2335859, 4953324, 1557066, 3003226, 5835311, 7214849, 1675280, 2755795, 7679796, 6588744, 6037572, 1898931, 161634, 4769500, 3683284, 2155048, 5878137, 6051124, 2035316, 5968625]省略以下700w+个数据..
希尔排序
shell排序800w个元素耗时2079ms
排序后arr3=[0, 0, 3, 6, 6, 7, 9, 9, 9, 11, 12, 15, 16, 17, 18, 19, 20, 21, 22, 23]省略以下700w+个数据..
---------------------------------------------------------------
排序前arr4=[2335859, 4953324, 1557066, 3003226, 5835311, 7214849, 1675280, 2755795, 7679796, 6588744, 6037572, 1898931, 161634, 4769500, 3683284, 2155048, 5878137, 6051124, 2035316, 5968625]省略以下700w+个数据..
归并排序
归并排序800w个元素耗时1123ms
排序后arr4=[0, 0, 3, 6, 6, 7, 9, 9, 9, 11, 12, 15, 16, 17, 18, 19, 20, 21, 22, 23]省略以下700w+个数据..
Process finished with exit code 0
数据有序的情况下
数据有序的情况下
---------------------------------------------------------------
排序前arr1=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]省略以下700w+个数据..
堆排序
堆排序800w个元素耗时665ms
排序后arr1=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]省略以下700w+个数据..
---------------------------------------------------------------
排序前arr2=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]省略以下700w+个数据..
快速排序
随机快速排序800w个元素耗时350ms
排序后arr2=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]省略以下700w+个数据..
---------------------------------------------------------------
排序前arr3=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]省略以下700w+个数据..
希尔排序
shell排序800w个元素耗时109ms
排序后arr3=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]省略以下700w+个数据..
---------------------------------------------------------------
排序前arr4=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]省略以下700w+个数据..
归并排序
归并排序800w个元素耗时315ms
排序后arr4=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]省略以下700w+个数据..
Process finished with exit code 0
由以上性能测试可知,快排在数据无序的情况下是4种平均时间复杂度O(NlogN)的排序算法中最优的。
swap函数
public static void swap(int[] arr ,int i,int j){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
冒泡排序 Bubble
public static void bubble(int[] arr){
System.out.println("冒泡排序");
for (int j = 0; j < arr.length; j++) {
for (int i = 0; i < arr.length - 1 -j; i++) {
if(arr[i] > arr[i+1]){
swap(arr,i,i+1);
}
}
}
}
选择排序 Choose
public static void choose(int[] l){
System.out.println("简单选择排序");
for (int i = 0; i < l.length-1; i++) {
int index = 0;
for (int j = 0; j < l.length-i; j++) {
if(l[j]>l[index]){
index = j;
}
}
swap(l,index,l.length-i-1);
}
}
插入排序 Insert
public static void insert(int[] l) {
System.out.println("简单插入排序");
for (int i = 1; i < l.length; i++) {
int val = l[i];
int index = i-1;
while(index >=0 && val<l[index]){
l[index+1] = l[index];
index--;
}
l[index+1] = val;
}
}
希尔排序 Shell
public static void shell(int[] l){
System.out.println("希尔排序");
int len = l.length;
int step = len;
int val = 0;
int index = 0;
//最后一步步长为1 1/2==0
while((step /= 2) > 0){
//一共有step组 每组有一个内循环来处理
// 这里i从step开始 不是从length-step开始 类比插入排序
for (int i = step; i < len; i++) {
//内层循环 每个循环解决一组
val = l[i];
index = i-step;
while(index>=0 && val < l[index]){
l[index+step] = l[index];
index-=step;
}
l[index+step]=val;
}
}
}
快速排序 Fast
public static void fast(int[] l){
System.out.println("快速排序");
Random random = new Random();
int len = l.length;
fast(l,0,len-1,random);
}
private static void fast(int[] l, int i,int j,Random random){
if(j<=i){
return;
}
int randIndex = random.nextInt(j-i+1)+i;
swap(l,randIndex,i);
int target = l[i];
int left = i; // 是i不是i+1!!!
int right = j;
while(left != right){
while (right!=left && l[right]>= target){//停止条件是相遇 或者遇到比target小的元素
right--;
}
while(left!=right && l[left]<=target){//停止条件是相遇 或者遇到比target大的元素
left++;
}
swap(l,right,left);
}
swap(l,right,i);
fast(l,i,right-1,random);
fast(l,right+1,j,random);
}
归并排序 Merge
public static void mergeSort(int[] l){
System.out.println("归并排序");
int len = l.length;
int[] tmp = new int[len];
mergeSort(l,tmp,0,len-1);
}
private static void mergeSort(int[] l , int [] tmp,int i,int j){
if(i>=j){
return;
}else{
int mid = (i+j)/2;
mergeSort(l,tmp,i,mid);
mergeSort(l,tmp,mid+1,j);
merge2SortedList(l,i,mid,j,tmp);
}
}
private static void merge2SortedList(int[] l ,int left, int mid, int right, int[] tmp){
int index = left;
int i = left;
int j = mid+1;
while(i<= mid && j<=right){
if(l[i]<=l[j]){
tmp[index] = l[i];
i++;
index++;
}else{
tmp[index]=l[j];
j++;
index++;
}
}
//有一边已经全部拷完了
while(i<=mid){
tmp[index] = l[i];
index++;
i++;
}
while(j<=right){
tmp[index] = l[j];
index++;
j++;
}
//往原始数组拷
for (int k = left; k <= right; k++) { // 是<=不是<
l[k] = tmp[k];
}
}
堆排序 Heap
public static void heapSort(int[] arr){
System.out.println("堆排序");
int lastIndex = arr.length-1;
//(arr.length-2)/2 是最后一个有子节点的节点下标
for (int index = (arr.length-2)/2; index >= 0 ; index--) {
// 构建初始的全局大顶堆 大概是nlogn的时间复杂度
adjustHeap(arr,index,lastIndex);
}
for(;lastIndex>=1;lastIndex--){
// 将堆顶元素与堆最后一个元素互换
swap(arr,0,lastIndex);
// 将堆的size-1 重新构建大顶堆
//大约logn的时间复杂度
adjustHeap(arr,0,lastIndex-1);
}
}
private static void adjustHeap(int[] arr,int root,int lastIndex){ // 根据last,调整使之成为大顶堆
int current = root;
int left = 2*current+1;
int right = 2*current+2;
// 连左孩子都没有 直接无需调整
if(left>lastIndex){
return;
// 如果有左孩子但没右孩子
} else if(right>lastIndex){
//如果左孩子比自己大
if(arr[left]>arr[current]){
//交换
swap(arr,left,current);
//交换后要重新以左孩子为起点 向下adjust堆
adjustHeap(arr,left,lastIndex);
}
//既有左孩子又有右孩子
}else{
//先找最大的孩子
if(arr[right]> arr[left]){
//如果左孩子大 再跟current比
if(arr[right]>arr[current]){
swap(arr,right,current);
//交换后要重新以右孩子为起点 向下adjust堆
adjustHeap(arr,right,lastIndex);
}
}else{
if(arr[left]>arr[current]){
//如果右孩子大 再跟current比
swap(arr,left,current);
//交换后要重新以左孩子为起点 向下adjust堆
adjustHeap(arr,left,lastIndex);
}
}
}
}