基本数据排序
2019-07-12 本文已影响0人
CODERLIHAO
一、冒泡排序
/**
* 冒泡排序
*/
private static void sort1() {
int[] array = generateArray();
long startTime = System.currentTimeMillis();
System.out.println(Arrays.toString(array));
for(int i = array.length - 1; i > 0; i--) {
for(int j = 0; j < i; j++) {
if(array[j] > array[j + 1]) {
swap(array, j, j + 1);
}
}
System.out.println(Arrays.toString(array));
}
System.out.println(System.currentTimeMillis() - startTime);
if(array.length<=100){
System.out.println(Arrays.toString(array));
}
}
public static void swap(int[] arr, int a, int b) {
arr[a] = arr[a] + arr[b];
arr[b] = arr[a] - arr[b];
arr[a] = arr[a] - arr[b];
}
/**随机生成数据*/
private static int[] generateArray(){
int length = 10_0000;
Random random = new Random(System.currentTimeMillis());
int[] array = new int[length];
for (int i = 0; i < length; i++) {
array[i] = random.nextInt(100);//[0,100)
}
return array;
}
冒泡排序
二、选择排序
原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。
int[] array = generateArray();
long startTime = System.currentTimeMillis();
int min;
for (int i = 0; i < array.length; i++) {
//给定一个变量，假定该位置是最小值
min = i;
for (int j = i+1; j < array.length; j++) {
if(array[j] < array[min]){
//找到比min位置还小的，将j的位置给min
min = j;
}
}
//检查位置有没有变化
if(min != i){
swap(array,i,min);
}
}
System.out.println(System.currentTimeMillis() - startTime);
if(array.length<=100){
System.out.println(Arrays.toString(array));
}
选择排序
三、插入排序
int[] array = generateArray();
long startTime = System.currentTimeMillis();
for (int i = 1; i <array.length ; i++) {
int temp = array[i];
for (int j = i-1; j >=0 ; j--) {
if(array[j] > temp){
array[j+1] = array[j];
}else {
array[j+1] = temp;
break;
}
}
}
System.out.println(System.currentTimeMillis() - startTime);
if(array.length<=100){
System.out.println(Arrays.toString(array));
}
插入排序
四、快速排序
我们先定义一个概念：基准值
其实就是一个值，一般取数组的开始和结尾位置的数。
对于一个数组，我们假定有2个哨兵，哨兵甲从左向右查找比基准值大的数，
哨兵乙从右向左查找比基准值小的值。
现在我们定义了基准值3，哨兵甲开始从左向右找比3大的数，此时找到了7，哨兵乙从右向左找比基准数小的值，找到了的1，
交换7和1，此时哨兵甲位置的数据是1，哨兵乙位置的数据是7，因为甲乙哨兵没有碰面，继续查找，哨兵乙继续查找比基准值3小的数，找到了此时位于哨兵甲位置的数子1，甲乙哨兵碰面了，，乙哨兵停下来了，甲哨兵因为条件不满足不能再查找了。
碰面后，交换基准值和碰面位置的数据
此时数组被分为2组，因为左边的不满足条件，将右边的再一次查找交换，此时的基准值为15
重新分配哨兵甲乙，开始查找，哨兵乙查找比基准值15小的数，就是4，哨兵乙停下来，哨兵甲开始找比15大的
没有找到，这时候甲乙碰面
交换15和4数据，这个时候又产生了一个新的分组，新的基准值为4，继续找。。。
最后就变成
private static void quicksort(int[] array,int left,int right){
if(left > right)
//注意递归退出的条件
return;
//基准值,现在假定基准值就是left位置上的数
int basic = array[left];
//假设哨兵甲的位置在i处，哨兵甲专门寻找比基准值大的数
int i = left;
//假设哨兵乙的位置在j处，哨兵甲专门寻找比基准值小的数
int j = right;
while (i != j){
//2个哨兵没有喷到一起，就一直检查下去
//先从哨兵乙开始从右向左开始检查，找到比基准数小的数就可以停下来
while (array[j] >= basic && i<j){
j--;
}
//等哨兵乙停下来后，哨兵甲开始从左向右开始检查，找到比基准数大的数就可以停下来
while (array[i] <= basic && i<j){
i++;
}
//等到哨兵甲停下来后，比较2个哨兵的位置
if(i!=j) {
//交换哨兵甲乙位置的数据
swap(array,i,j);
}
}
//2个哨兵碰头了
array[left] = array[i];
//将基准值赋值给碰头的位置，此时在基准数左边的都比基准值小，在基准数右边的都比基准值大
array[i] = basic;
//分成了2组数组，递归调用
quicksort(array,left,i-1);
quicksort(array,j+1,right);
}
快速排序
快速排序的确是快，我的普通i5cpu,处理10万数据也就几十毫秒，但是因为是递归调用，快速排序的性能取决于递归树的深度。
