三大普通排序方法
冒泡排序
简单来说，冒泡，就和水里面吹泡泡一样，只不过我们多次循环，每次只看相邻的两个数，加入顺序不符合我们的要求，就交换他们的位置。
/**冒泡排序*/
public int[] bubbleSort(int[] arr){
int temp;
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length-i-1; j++) {
if(arr[j]>arr[j+1]){
temp =arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
return arr;
}
/**
选择排序
选择排序，顾名思义，就是每一次选择最小(最大)的数，去放在你想放的位置，比如第一次选择最小(最大)的数放在最前面，第二次找到除第一个数以外剩下的数中的最小(最大)的数放在第二个位置，依次类推。
/**选择排序*/
public int[] chooseSort(int[] arr){
int temp;
for (int i = 0; i < arr.length-1; i++) {
for (int j = i+1; j < arr.length; j++) {
if(arr[i]>arr[j]){
temp=arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}
插入排序
插入排序就和你打牌时理牌一个样，保证你的前面每一次排序都是有序的就行。
/**插入排序*/
public int[] insertSort(int[] arr){
int temp;
//外层循环，控制第几个数字进行循环
for(int i = 1; i < arr.length; i++) {
//内层循环控制进行与之前的比较
for (int j = i; j > 0; j--) {
if (arr[j-1] > arr[j]){
int t = arr[j-1];
arr[j-1] = arr[j];
arr[j] = t;
}else {
//一旦前面的没有这个数字大时，即可结束内层循环，减少时间复杂度
break;
}
}
}
return arr;
}
衍生的一些其他排序方法
最简单的使用排序
使用集合自带的sort函数对数组进行排序
Arrays.sort(arr);
快速排序
快速排序稍微复杂一点，但是真要简单的说，就是我们两个人往中间走，假如左边的比右边的大，我们两换个位置，大的数组下标继续往中间走，最后当我们两遇见的时候，起码可以保证前半段数据和后半段数据都是相对有序的了，在使用递归的方式，对前半段数据和后半段数据进行调用方法，就搞定了。
/**快速排序*/
public void fastSort(int[] arr,int left,int right){
int start,end,temp,t;
if(left>right){
return;
}
start = left;
end = right;
//保存每一次进来的初始值
temp = arr[left];
while ( start<end ){
//判断是否需要需要往中间移
while ( temp<=arr[end] && start<end ){
end--;
}
while ( temp>=arr[start] && start<end ){
start++;
}
//不能往中间移，交换位置
if(start<end){
t = arr[start];
arr[start] = arr[end];
arr[end] = t;
}
//将改变后的值和第一个基准值进行交换
arr[left] = arr[start];
arr[start] = temp;
//递归调用
fastSort(arr,left,end-1);
fastSort(arr,end+1,start);
}
}
希尔排序
这种排序方式说难不难，但是不太好理解。简单就是，我们将数组的长度拆分，假如我有10个数，第一轮就让我的第一个数和第六个数进行比较，第二个数和第七个数进行比较，以此类推，第一轮结束后，在将步长缩短一半，这时候就变成了，第一个数和第三个数第五个数和第7个数和第9个这样子进行比较，第三轮再将步长缩短一半为1即剩下的所有数进行排序。这样子的希尔排序，看起来比较的次数多了，但是他们其实比较的次数会少很多，甚至于在力扣测试中，速度会快几倍以上。
/**希尔排序*/
public int[] hillSort(int[] arr){
int temp;
for (int k = arr.length / 2; k > 0; k /= 2) {
for (int i = k; i < arr.length; i++) {
for (int j = i; j >= k; j -= k) {
if (arr[j - k] > arr[j]) {
temp = arr[j - k];
arr[j - k] = arr[j];
arr[j] = temp;
}
}
}
}
return arr;
}
测试一下
输入数组的方式或许有点low，不要在意这些细节，凡人！
public static void main(String[] args) {
int[] arr = new int[5];
Scanner sc = new Scanner(System.in);
for (int i = 0; i < arr.length; i++) {
System.out.print("请输入你的数组第"+(i+1)+"个数：");
arr[i] = sc.nextInt();
}
System.out.print("你输入的数组为：");
for (int i: arr) {
System.out.print(i+" ");
}
// new TestSort().fastSort(arr,0,arr.length-1);
// arr = new TestSort().bubbleSort(arr);
// arr = new TestSort().chooseSort(arr);
// arr = new TestSort().insertSort(arr);
// arr = new TestSort().hillSort(arr);
Arrays.sort(arr);
System.out.print("排序后的数组为：");
for (int i: arr) {
System.out.print(i+" ");
}
}
