1）冒泡排序
1.1 图解演示
2）选择排序
import java.text.SimpleDateFormat;import java.util.Date;/*** 选择排序*/public class chooseSort {public static void selectSort(int[] arr){for (int i = 0; i < arr.length; i++) {int minIndex = i;int min = arr[i];for (int j = i+1; j < arr.length; j++) {if (min > arr[j]){//说明最小值不是min，然后重置min = arr[j];minIndex = j;}}//交换arr[minIndex] = arr[i];arr[i] = min;}}public static void main(String[] args) {int arr [] = new int[80000];for (int i = 0; i < arr.length; i++) {arr[i] = (int)(Math.random() * 800000);}Date date1 = new Date();SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd:HH:mm:ss");String data1Str = simpleDateFormat.format(date1);System.out.println("排序前时间："+ data1Str);selectSort(arr);Date date2 = new Date();String date2Str = simpleDateFormat.format(date2);System.out.println("排序后时间："+ date2Str);//System.out.println(Arrays.toString(arr));}}
3）插入排序
import java.text.SimpleDateFormat;import java.util.Date;public class InsertSort {public static void insertSort(int [] arr){for (int i = 1; i < arr.length; i++) {int insertVal = arr[i];int insertIndex = i-1;//arr[1]前面这个数的下标//给insertVal找到插入位置//insertIndex>=0保证给insertVal插入的位置不越界//insertVal < arr[insertIndex]待插入的数，还没有找到插入的位置//就需要arr[insertIndex]后移while(insertIndex >= 0 && insertVal < arr[insertIndex]){arr[insertIndex+1] = arr[insertIndex];insertIndex --;}//出来就是找到插入的位置，即insertIndex+1arr[insertIndex+1] = insertVal;}}public static void main(String[] args) {int [] arr = new int[80000];for (int i = 0; i < 80000; i++) {arr[i] = (int)(Math.random()*800000);}Date date1 = new Date();SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd:HH:mm:ss");String format1 = simpleDateFormat.format(date1);System.out.println(format1);insertSort(arr);Date date2 = new Date();String format2 = simpleDateFormat.format(date2);System.out.println(format2);//System.out.println(Arrays.toString(arr));}}
4)希尔排序（插入排序改进版）
在这里插入图片描述
4.1希尔的交换法
import java.text.SimpleDateFormat;import java.util.Date;/*** 希尔排序（缩小增量排序）,交换的速度并不快*/public class SellSort {public static void sellSort(int [] arr){//第一轮排序将10个数据分成5组int temp = 0;int gap = arr.length/2;while(gap>=1) {for (int i = gap; i < arr.length; i++) {//遍历各组中所有元素（共五组，每组两个元素），步长为5for (int j = i - gap; j >= 0; j -= gap) {//如果当前元素大于加上步长元素交换if (arr[j] > arr[j + gap]) {temp = arr[j];arr[j] = arr[j + gap];arr[j + gap] = temp;}}}gap = gap/2;}}public static void main(String[] args) {int [] arr = new int[80000];for (int i = 0; i < 80000; i++) {arr[i] = (int)(Math.random()*800000);}Date date1 = new Date();SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd:HH:mm:ss");String format1 = simpleDateFormat.format(date1);System.out.println(format1);sellSort(arr);Date date2 = new Date();String format2 = simpleDateFormat.format(date2);System.out.println(format2);}}
4.2希尔的移位法
import java.text.SimpleDateFormat;import java.util.Date;/*** 希尔排序（缩小增量排序）,交换的速度并不快*///移位法public static void sellSort2(int [] arr){//第一轮排序将10个数据分成5组int temp = 0;int gap = arr.length/2;while(gap >= 1) {for (int i = gap; i < arr.length; i++) {int insertVal = arr[i];int insertIndex = i - gap;//移位找位置while(insertIndex >= 0 && arr[insertIndex] > arr[i]){arr[i] = arr[insertIndex];insertIndex -= gap;}//插入if (insertIndex + gap != i){arr[insertIndex+ gap] = insertVal;}}gap = gap/2;}}public static void main(String[] args) {int [] arr = new int[80000];for (int i = 0; i < 80000; i++) {arr[i] = (int)(Math.random()*800000);}Date date1 = new Date();SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd:HH:mm:ss");String format1 = simpleDateFormat.format(date1);System.out.println(format1);sellSort2(arr);Date date2 = new Date();String format2 = simpleDateFormat.format(date2);System.out.println(format2);//System.out.println(Arrays.toString(arr));}}
可以看到希尔排序的移位法的效率大大提高。当你改成8w、80w都是可以1秒出结果，但是插入排序80w需要很长时间大概几分钟。
5）快速排序
package sort;import java.text.SimpleDateFormat;import java.util.Date;public class QuickSort {public static void quickSort(int [] arr,int left,int right){int l = left; //左下标int r = right; //右下标int pivot = arr[(left+right)/2];//while循环的目的是让比pivot小的放到左边，大的放到右边int temp = 0;while (r > l){while (arr[l] < pivot){//在pivot左边一直找，找到大于等于pivot的值l += 1;}while(arr[r] > pivot){//在pivot右边一直找，找到小于等于pivot的值r -= 1;}//如果l>=r成立，说明排序成功if (l >= r){break;}//交换temp = arr[l];arr[l] = arr[r];arr[r] = temp;//交换完成后发现值arr[l] = pivot，需要往前再走一步if (arr[l] == pivot){l++;}//交换完成后发现值arr[r] = pivot，需要往前再走一步if (arr[r] == pivot){r--;}}//如果l == r，必须让l++，r--，否则死循环出不去if (l == r){l++;r--;}//向左递归if (left < r){quickSort(arr,left,r);}//向右递归if (right > l){quickSort(arr,l,right);}}public static void main(String[] args) {int [] arr = new int[8000000];for (int i = 0; i < 8000000; i++) {arr[i] = (int)(Math.random()*80000000);}Date date1 = new Date();SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd:HH:mm:ss");String format1 = simpleDateFormat.format(date1);System.out.println(format1);quickSort(arr,0,arr.length-1);Date date2 = new Date();String format2 = simpleDateFormat.format(date2);System.out.println(format2);//System.out.println(Arrays.toString(arr));}}
800w数据3秒
上面代码听完课，研究一下午还是没太懂尤其是递归那块，于是又查了好多资料学习
package sort;import java.text.SimpleDateFormat;import java.util.Arrays;import java.util.Date;public class QuickSort {public static void quickSort1(int[] arr, int start, int end) {//1.找到中轴getIndex()//2.左递归//3.右递归if (start < end) {int index = getIndex(arr, start, end);quickSort1(arr, start, index - 1);quickSort1(arr, index + 1, end);}}//找中轴又分为：//1.取一个中轴，随便取//2.（如果中轴是第一个位置）那么就先从右往左找，找到小于等于中轴的数，然后把找到的数赋值给arr[start]//3.从左往右找，找到大于等于中轴的数，把找到的数赋给arr[end]//4.最后再把pivot赋给arr[start]//5.返回startpublic static int getIndex(int[] arr, int start, int end){int pivot = arr[start];while (start < end){//从右往左找while (arr[end] >= pivot && start < end){end --;}arr[start] = arr[end];while(arr[start] <= pivot && start < end){start++;}arr[end] = arr[start];}arr[start] = pivot;return start;}public static void main(String[] args) {int[] arr = new int[]{-1,0,5,2,8,-1,0,0,0};// for (int i = 0; i < 4; i++) {// arr[i] = (int)(Math.random()*800000);// }Date date1 = new Date();SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd:HH:mm:ss");String format1 = simpleDateFormat.format(date1);System.out.println(format1);quickSort1(arr, 0, arr.length - 1);Date date2 = new Date();String format2 = simpleDateFormat.format(date2);System.out.println(format2);System.out.println(Arrays.toString(arr));}}
6)归并排序
package sort;import java.util.Arrays;public class MergeSort {/**** @param arr 排序的原始数组* @param start 左边初始索引* @param end 右边初始索引* @param mid 中间索引* @param temp 中转的数组*/public static void merge(int[] arr, int start, int end, int mid,int[] temp){int i = start; //初始化i，左边有序序列的初始索引int j = mid + 1; //初始化j，右边有序序列的初始索引int t = 0; //指向temp数组的当前索引//（1）//先把左右两边(有序)的数据按照规则填充到temp数组//直到左右两边的有序序列，有一边处理完毕while (i <= mid && j <= end){//如果左边有序序列的当前元素，小于等于右边有序序列的当前元素//即将左边的当前元素，拷贝到temp数组//然后t++，i++if (arr[i] <= arr[j]){temp[t] = arr[i];t++;i++;}else {//反之，右边有序序列当前元素小于左边，将右边有序序列当前元素拷贝到temptemp[t] = arr[j];t++;j++;}}//（2）//把有剩余数据的一边的数据依次填充到tempwhile (i <= mid){//说明左边有序序列剩余元素还有剩余，全部填充到temptemp[t] = arr[i];t++;i++;}while (j <= end){//说明右边有序序列剩余元素还有剩余，全部填充到temptemp[t] = arr[j];t++;j++;}//（3）//将temp元素拷贝到arr//注意并不是每次都拷贝所有t = 0;int tempLeft = start;//while (tempLeft <= end){//第一次合并tempLeft = 0；right = 1arr[tempLeft] = temp[t];t++;tempLeft ++;}}//分+合方法public static void mergeSort(int[] arr,int start,int end,int[] temp){if (start < end){int mid = (start+end)/2; //中间索引//向左递归进行分解mergeSort(arr,start,mid,temp);//向右递归进行分解mergeSort(arr,mid+1,end,temp);//合并merge(arr, start,end,mid,temp);}}public static void main(String[] args) {int arr[] = {8,4,5,7,1,3,6,2};int temp[] = new int[arr.length];//归并排序需要一个额外空间mergeSort(arr,0,arr.length-1,temp);System.out.println(Arrays.toString(arr));}}
如果觉得《算法 - 排序算法 （算法学习）（冒泡 选择 插入 希尔 快排 归并）》对你有帮助，请点赞、收藏，并留下你的观点哦！
