排序
冒泡排序
两次for循环 一次循环可以将一个数据排好序,那两次for循环叠加就可以将整个数组的数据排好序。
//arr[i]>(<)arr[i+1] 交换
//走一轮用的代码
for(int i = 0;i<arr.length-1;i++){if(arr[i]>arr[i+1]){//交换//并且要注意 i<arr.length-1 因为交换条件是i+1 我们需要保证不溢出int temp = 0;temp = arr[i];arr[i]=arr[i+1];arr[i+1]=temp;}
}
//总代码
for(int j=0;j<arr.length;j++){for(int i = 0;i<arr.length-1;i++){if(arr[i]>arr[i+1]){//交换//并且要注意 i<arr.length-1 因为交换条件是i+1 我们需要保证不溢出int temp = 0;temp = arr[i];arr[i]=arr[i+1];arr[i+1]=temp;}
}
}
选择排序
游标 i 从左到右遍历数组,找到数组中最小值。让最小值和待排序数组中的第一位进行交换。
for(int j = 0;j<arr.length-1;j++){//等排到最后一个数字时,就已经排好顺序了,所以可以长度-1int min = arr[j];//先默认最小值是待排序数组中的第一个int index = j;//最小值的下标for(int i =j+1;i<arr.length;i++){//因为前面的已经排好序了,我们只要从待排的数据后一个开始排序。if(arr[i]<min){min = arr[i];index = i;}}arr[index] = arr[j];arr[j] = min;
}
插入排序
//先令第一个元素有序,让i为第二个元素。i不断遍历,i的循环下套一个j的循环,j循环的目的是检测数组是否有序。如果无序,那么交换位置。
for(int i = 1;i<arr.length;i++){for(int j = i-1;j>=0;j--){if(arr[j]>arr[j+1]){int temp = arr[j];arr[j]=arr[j+1];arr[j+1] = arr[j];}}
}
希尔排序
//就是插入排序的升级版。先分块 再插入排序。
for(int gep = arr.length/2;gep>0;gep/=2) {//i保证的是对每个分块都进行排序for(int i = gep;i<arr.length;i++) {for(int j = i-gep;j>=0;j-=gep) {if(arr[j]>arr[j+gep]) {int temp =arr[j];arr[j]=arr[j+gep];arr[j+gep] =temp;}}}}
基数排序
package com.qcby;
import java.util.Arrays;
public class ShellSort {public static void main(String[] args) {int arr[] = new int[] {654,123,7,12,987,122,234,18,46,10};sort(arr);System.out.println(Arrays.toString(arr));}public static void sort(int[] arr) {//定义二维数组来当做桶int[][] bucket = new int[10][arr.length];//定义一个一维数组来当做统计数据记录器int[] count = new int[10];//找到数组当中的最大数int max = arr[0];for(int i = 0;i<arr.length;i++) {if(arr[i] > max) {max = arr[i];}}//得到最大值的位数int maxLength = (max + "").length();int n = 1;for(int h = 0;h<maxLength;h++) {for(int i = 0;i<arr.length;i++) {int element = arr[i] / n % 10; //读取出每个数组个位的值int num = count[element]; //根据个位的值的值找到桶内有多少数据bucket[element][num] = arr[i]; //将数据放入到桶当中count[element] = count[element]+1; //数据记录器响应位置+1}//将数据取出int index = 0;for(int k = 0; k<10;k++){if(count[k]!=0){for(int l = 0; l<count[k];l++){arr[index] = bucket[k][l];index++;}count[k] = 0; //清空桶记录器}}n= n * 10;}}
}
归并排序
public void mergeSort(int[] arr, int low, int high) {// 递归结束条件:当low等于high时,表示已经只剩一个元素,不需要再继续递归划分了if (low < high) {// 计算中间位置,对左右两个子数组分别进行递归划分int mid = (low + high) / 2;mergeSort(arr, low, mid);mergeSort(arr, mid + 1, high);// 将左右两个有序子数组合并为一个有序数组merge(arr, low, mid, high);}
}
/*** 合并左右两个有序子数组为一个新的有序数组* @param arr 原数组* @param low 左子数组的起始位置* @param mid 左子数组的结束位置,同时也是右子数组的起始位置-1* @param high 右子数组的结束位置*/
public void merge(int[] arr, int low, int mid, int high) {// 新建一个临时数组来存储排序后的结果int[] temp = new int[high - low + 1];int i = low; // 左子数组起始位置int j = mid + 1; // 右子数组起始位置int k = 0; // 临时数组的下标// 将左右两个子数组中较小的元素依次放入临时数组中while (i <= mid && j <= high) {if (arr[i] <= arr[j]) {temp[k++] = arr[i++];} else {temp[k++] = arr[j++];}}// 如果左子数组还有剩余,则将其全部复制到临时数组中while (i <= mid) {temp[k++] = arr[i++];}// 如果右子数组还有剩余,则将其全部复制到临时数组中while (j <= high) {temp[k++] = arr[j++];}// 将临时数组中的元素复制回原数组中for (int p = 0; p < temp.length; p++) {arr[low + p] = temp[p];}
}
快速排序
package com.qcby;
import java.util.Arrays;
public class QuickSort {public static void main(String[] args) {int arr[] = new int[] {5,7,4,2,0,3,1,6};quickSort(arr, 0, arr.length-1);System.out.println(Arrays.toString(arr));}public static void quickSort(int[] arr,int left,int right) {if(left >= right) { // left > right | left == rightreturn;}int base = arr[left]; //基准数int i = left; //两个游标int j = right;//当 i 和 j 不相遇的时候,重复以下过程while(i != j) {while(arr[j]>=base && i<j) {j--;}while(arr[i]<=base && i<j) {i++;}//数据交换int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}//相遇位置的数和基准数交换arr[left] = arr[i];arr[i] = base;quickSort(arr, left, i-1,i,j);quickSort(arr, i+1, right,i,j);}}