排序算法---希尔插入选择冒泡快速测试下 - 黑马程序员技术交流社区

package com.liubo.test;
import java.io.IOException;
import java.util.Arrays;
public class SortDemo02 {
public static void main(String[] args) throws InterruptedException, IOException {
int [] arr1=new int[10000];
int [] arr2=new int[10000];
int [] arr3=new int[10000];
int [] arr4=new int[10000];
int [] arr5=new int[10000];
int [] arr6=new int[10000];
//随机生成10000个数据
for(int i=0;i<10000;i++){
arr1[i]=(int) (Math.random()*1000);
arr2[i]=arr1[i];
arr3[i]=arr1[i];
arr4[i]=arr1[i];
arr5[i]=arr1[i];
arr6[i]=arr1[i];
}
System.out.println("测试数据个数:"+arr1.length);
long start=System.currentTimeMillis();
//自带排序
Arrays.sort(arr1); //据说这个有两种排序基本数据类型用快递排序饮用对象用的是堆排序
long end=System.currentTimeMillis();
System.out.println("Arrays.Sort 用时:"+(end-start));
start=System.currentTimeMillis();
//冒泡排序
bubbleSort(arr2);
end=System.currentTimeMillis();
System.out.println("bubbleSort 用时:"+(end-start));
//选择排序
start=System.currentTimeMillis();
selectSort(arr3);
end=System.currentTimeMillis();
System.out.println("selectSort 用时:"+(end-start));
start=System.currentTimeMillis();
//插入排序
insertSort(arr4);
end=System.currentTimeMillis();
System.out.println("insertSort 用时:"+(end-start));
start=System.currentTimeMillis();
//希尔排序
myShellSort(arr5);
end=System.currentTimeMillis();
System.out.println("shellSort 用时:"+(end-start));
//快速排序分治法
start=System.currentTimeMillis();
fastSort(arr6);
end=System.currentTimeMillis();
System.out.println("fastSort 用时:"+(end-start));
}
/*
* 冒泡排序从最末尾的数开始来和前一个比较每次将最小的浮到最上面
* */
private static void bubbleSort(int[] arr) {
boolean flag=true; //用来判断如果一次冒泡下来没变化就说么已经排序好了后面就不用排序了
for(int i=0;flag&&i<arr.length-1;i++){
flag=false;
for(int j=arr.length-1;j>i;j--){
if(arr[j]<arr[j-1]){
swap(arr,j,j-1);
//交换了说明变化了
flag=true;
}
}
}
//System.out.println(Arrays.toString(arr));;
}
/*
* 每次遍历都找出最小的
* 和被遍历的最前面的换位置这样每次都将最小的放在前面了
* */
private static void selectSort(int[] arr) {
int index=0; //默认最小的在0
for(int i=0;i<arr.length-1;i++){
index=i; //因为每次选择排序后最小的都是剩下的最前面的那个
for(int j=i+1;j<arr.length;j++){
if(arr[j]<arr[index]){
index=j;
}
}
if(index!=i)
swap(arr,index,i);
}
//System.out.println(Arrays.toString(arr));
}
//插入排序
private static void insertSort(int[] arr) {
int index=0; //被比较的位置
int key=0;// 去比较的数的值
for(int i=1;i<arr.length;i++){ //从第2个开始与前面的比较遇到第一个比他小的数停留在那个数去的前一个位置
index=i-1;
key=arr[i];
//循环
while(index>=0 && key<arr[index]){
//前面大的数后后移一位
arr[index+1]=arr[index];
index--; //在和前面的比较
}
//当遇到比自己晓得或者在最前面的时候
arr[index+1]=key; //key的位置赵大鹏
}
// System.out.println(Arrays.toString(arr));
}
//希尔排序
private static void myShellSort(int[] arr) {
int key=0; //某个位置的数要去和前面的数比较的
int j=0;
for(int d=arr.length/2 ; d>0 ;d/=2){
//将这些坐标的数 3 0是一对 4 1 5 2 类推就是当前位置当前位置-d
for(int i=d;i<arr.length;i++){
key=arr[i]; //拿出来每次组里面的最后一个数
//System.out.println(key);
//在每组中插入排序
for(j=i; j>=d;j-=d){
//开始循环
if(key < arr[j-d]){ //如果小于就将前面大的数移动后面那个空位置
arr[j]=arr[j-d];
}
else{
break;
}
}
arr[j]=key;
}
}
// System.out.println(Arrays.toString(arr));
}
/*
* 分治法先去一个数将数组中小于他的数放在他的左边大于他的数放在他的右边从右边找比他小的j 左边找比他大的i j==i exit
* 挖坑填数在依次对左边和右边这样
*
* */
private static void fastSort(int[] arr) {
int l=0,r=arr.length-1;
fast_sort(arr,l,r);
//System.out.println(Arrays.toString(arr));
}
private static void fast_sort(int[] arr, int l, int r) {
int x=arr[l]; //每次将进来的这一段数组的最前的数为标准晓得填到他的左边大的填到他的右边
int i=r;
int j=l;
if(l<r){
while(j<i){
//右边大的话就一直遍历下去知道找到第一个小的
for(;j<i&&arr[i]>=x;i--);
//小的听到最前面的位置
if(j<i)
arr[j++]=arr[i]; //这时候i的位置空了
//遍历左边的
for(;j<i&&arr[j]<x;j++);
//左边的移到右边空的位置
if(j<i)
arr[i--]=arr[j];
}
//最后i==j的时候
arr[i]=x;
//此时X为中间分为两段分别递归
if(l<i-1)
fast_sort(arr,l,i-1);
if(r>i+1)
fast_sort(arr,i+1,r);
}
}
//swap的
public static void swap(int[] arr, int j,int k){
arr[j]=arr[j]^arr[k]; // 5^3=X --->5=X
arr[k]=arr[j]^arr[k]; //3=X^3=5
arr[j]=arr[j]^arr[k]; // X=X^5=3 换了
}
}

复制代码