java基本排序算法-插入排序-快速排序-选择排序-冒泡排序

xiaoxiao2021-02-28  52

四个基本的排序算法

/** * 排序的基本实现方法:插入、选择、冒泡、快速 */ public class SortImpl { /**目标待排序数组*/ private static int[] arr = {1,3,4,44,2,33,4,35}; public static void show(int [] arr){ for (int i = 0; i < arr.length; i++){ System.out.print(arr[i] + " "); } System.out.println(); } //一、插入排序 【先确定前面】 //思路: 在要排序的一组数中,假设前面(n-1)[n从2计算] 个数已经是排序的,要把第n个数插到前面的有序数中,使得这 n个数 //也是排好序的。!优势在于碰到它大于前面的数,就直接添加到此数的前面即可。否则一路进行交换处理,直至换到第一位 @Test public void test1(){ for (int i = 1; i < arr.length; i++) { //插入的值,从i -> lenth -1 for (int j = i; j > 0 && arr[j]<arr[j-1]; j--){ int temp = arr[j]; arr[j] = arr[j-1]; arr[j-1] = temp; } } show(arr); } //二、选择排序 【先确定前面】 //思路:外层遍历所有的元素,然后取出的元素和它后面的元素进行比较,找到最小值。最后放入第一位...N位 @Test public void test2(){ for (int i = 0; i < arr.length; i++) { int min = i; for (int j = i+1 ; j < arr.length; j++) { if(arr[j]<arr[min]){ min = j; } } if(i!=min){ int temp = arr[i]; arr[i] = arr[min]; arr[min] = temp; } } show(arr); } //三、冒泡排序 【先确定后面】 //思路:每次从第一个,持续和它的下一个比较,如果它比下一个大就交换,一次循环算出它尾部最大值。一共n-1次 //外层只控制遍历次数,内层用相邻2个数比较。 @Test public void test3(){ for (int i = 0; i < arr.length-1; i++) { //1个数时不需要操作。 for (int j = 0; j < arr.length-1-i; j++) { //-i是因为每次可以算一个最大的值,-1是防止越界 if(arr[j+1]<arr[j]){ int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } show(arr); } //四、快速排序: @Test public void test4(){ sortQuick(arr,0,arr.length-1); show(arr); } /** * 快速排序;分割数组 ----------详细看下面补充的示意图 * @param datas */ public static int QuickPartition(int[] datas, int left, int right) { int key = datas[left]; //基准位 while (left < right) { while (left < right && datas[right] >= key){ --right; } datas[left] = datas[right]; // 将比基准小的元素移到低位,此时right位应=key,会被下面赋值替换,所以不用进行一个完整的换位置。 while (left < right && datas[left] <= key){ ++left; } datas[right] = datas[left]; // 将比基准大的元素移到高位,此时left应=key,同上理,会被后续赋值替换,只进行一般的换位置。 } datas[left] = key; // 当left == right,完成一趟快速排序,此时需要补上基准值。 return left; } /** * 快速排序;递归返回数组 * @param datas */ public static int[] sortQuick(int[] datas, int left, int right) { if (left < right) { int data = QuickPartition(datas, left, right); sortQuick(datas, left, data - 1); sortQuick(datas, data + 1, right); } return datas; } }

补充示意图:快速排序

 

 

转载请注明原文地址: https://www.6miu.com/read-1450261.html

最新回复(0)