一下介绍四种数组的常用排序方式
快速排序:时间复杂度最低,效率最高
package shuzu;
import java.util.Arrays;
import java.util.Random;
public class ArraySortsizhong {
public static void main(String[] args) {
int[] a=new int[10];//初始化里面所有元素为0
int[] b={1,2,3,4,5};//只能在声明时使用!
int[] c=new int[]{7,2,3,4,9,15,17};//可以在非声明时使用
/*
for循环的两种 idea快捷键itar iter(增强for循环)
*/
// //增强的for循环foreach,快捷键iter
// for (int i:b) {
// System.out.println(i);
// //foreach只能读不能写
// }
Random random=new Random();
Random传入的种子相同得到的随机数一样
// System.out.println(random.nextInt(100));
// //生成的数字包括0不包括100
// System.out.println(random.nextInt(100));
// System.out.println(random.nextInt(100));
for (int i = 0; i < a.length; i++) {
a[i]=random.nextInt(50);
}
System.out.println("数组最初的状态为:"+Arrays.toString(a));
//排序算法:插入选择,快速,冒泡,选择
//selectSort(a);
//insertSort(a);
//bubbleSort(a);
quickSort(a);
for (int i:a) {
System.out.println(i);
}
}
public static void selectSort(int[] a){
//选择排序:每次选择出最小的数放在当前循环的开始下标处
for (int i = 0; i < a.length; i++) {
int min=i;
for (int j = i+1; j < a.length; j++) {
if(a[min]>a[j]){
min=j;
}
}
if (min!=i){
change(a,i,min);
}
System.out.println(Arrays.toString(a));
}
}
public static void insertSort(int[] a){
//插入排序:假设前面的数字已经完成排序,当一个新数加入时,从后往前判断大小,直到冒泡把要插入的数字放入合适的位置-
for (int i = 1; i < a.length; i++) {
for (int j = i; j > 0; j--) {
if(a[j-1]>a[j]){
change(a,j-1,j);
}else {
break;
}
}
System.out.println(Arrays.toString(a));
}
}
public static void bubbleSort(int[] a){
//冒泡排序,第一遍通过两两的比较将最大的值下沉的最后一位,第二遍沉第二大的到倒数第二位....
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a.length-i-1; j++) {
if (a[j]>a[j+1]){
change(a,j,j+1);
}
}
System.out.println(Arrays.toString(a));
}
}
//快速排序:在数组中选取一个中间值,将他和最后一位的数字交换,定义一个index记录数组中有几个比[end](所选中的值)小的
//遍历整个数组,将index指向[0],将a[i]和a[end]进行比较,如果a[i]小于a[end],将a[i]和a[index]进行交换(把比标杆值小的数放在前面),并且把index++指向下一个位置
//最后将a[end]和a[index]交换,将比标杆大的数和比标杆小的数分成两堆,至于标杆的两侧
//最后递归调用该方法即可,递归的出口就是start>=end
public static void quickSort(int[] a){
quickSort(a,0,a.length-1);
}
public static void quickSort(int[] a,int start,int end){
if (start >= end) {
return;
}
Random random=new Random();
int index = random.nextInt(end - start + 1) + start;
change(a, index, end);
index = start;
for (int i = start; i < end; i++) {
if (a[i] < a[end]) {
change(a, index, i);
index++;
}
}
change(a,index,end);
quickSort(a,start,index-1);
quickSort(a,index+1,end);
}
public static void change(int[] a,int i,int j){
// a[i] ^=a[j];
// a[j] ^=a[i];
// a[i] ^=a[j];
int temp;
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}