java排序——冒泡、归并、选择、插入

排序的四种算法（参考邓俊辉老师的课程）

1.冒泡排序2.归并排序3.选择排序（后缀有序）4.插入排序（前缀有序）

1.冒泡排序

package yudi.sort; /* 冒泡排序无论如何改进，其O（n）最好为n，最坏为n^2 */ public class BubbleSort { /*这里我封装swap方法用来交换两个数，但是java是传值机制，在两个不同的方法中，作用域 不同，就算在swap方法中交换成功，但是出了方法后仍然是原来的值*/ public static void bubbleSort(int[] array,int n){ for (boolean sorted = false; sorted = !sorted; n--){ for (int i = 1; i < n; i++){ if (array[i] < array[i - 1]){ int temp = array[i]; array[i] = array[i - 1]; array[i - 1] = temp; sorted = false; } } } } //改进算法：记录最右边的逆序对的秩，下一次直接以这里为起点开始排序 public static void bubbleSortImprove(int[] array,int n){ while (0 < (n = findInversionSequenceIndex(array,n))); } //把最右边的逆序对的秩记录下来 public static int findInversionSequenceIndex(int[] array, int n){ int index = 0; for (int i = 1; i < n; i++) { if (array[i] < array[i - 1]) { int temp = array[i]; array[i] = array[i - 1]; array[i - 1] = temp; index = i;//记录最右边的逆序对的秩 } } return index; } //测试 public static void main(String[] args) { int[] array = {5,4,3,6,10,9,2,3,4}; // bubbleSort(array, array.length); bubbleSortImprove(array, array.length); for (int i =0; i < array.length; i++){ System.out.print(array[i] +" "); } } }

2.归并排序

归并排序的思想：分而治之——首先将数组分为两半递归排序，然后合并有序子序列 1.mergeSort

public static void mergeSort(int[] array, int low,int high){ if (high - low < 2) return;//递归基 int middle = (low + high) >> 1;//一分为二 mergeSort(array, low, middle); mergeSort(array, middle, high); merge(array, low, middle, high); Util.ptingArray(array);//这是自己编写的输出数组的方法 }

2.merge

public static void merge(int[] array, int low, int middle, int high){ int lB = middle - low ; int temp = low; int[] tempB = new int[lB]; for (int i = 0; i < lB; i++){//复制前子向量 tempB[i] = array[temp++]; } for (int i = low,j = 0,k = middle; j < lB ;){ if (k < high && array[k] < tempB[j]) array[i++] = array[k++]; if (high <= k || tempB[j] <= array[k]) array[i++] = tempB[j++]; } }

各个参数的意义如下图所示： 3.测试

public static void main(String[] args) { int[] array = {4,8,6,8,2,4,5,98}; mergeSort(array,0,array.length); System.out.println("===================="); Util.ptingArray(array); }

3.选择排序（后缀有序）

package yudi.sort; import yudi.util.Util; /* 选择排序：θ（n^2） 类似于起泡排序，每次排序后将最大者归位 只不过是直接与最后的元素交换 而不是像起泡一样逐个交换 */ public class SelectionSort { public static void selectionSort(int[] array, int n){ int maxIndex = 0; while (1 < n){ maxIndex = selectMaxIndex(array, n); int temp = array[maxIndex]; array[maxIndex] = array[n - 1]; array[n - 1] = temp; n--; } } public static int selectMaxIndex(int[] array, int n){//找出最大值的下标 int max = 0; for (int i = 0; i < n - 1; i++){ if (array[max] < array[i + 1]){ max = i + 1; } } return max; } //测试 public static void main(String[] args) { int[] array = {4,8,6,85,2,4,5,98}; selectionSort(array,array.length); Util.ptingArray(array); } }

4.插入排序（前缀有序）

/* 插入排序（基于列表实现）： 类似于一张一张摸牌的时候，将牌插入手牌一样 第一步比较， 第二步移动， 第三步插入 */ public class InsertionSort { public static void insertionSort(int[] array, int n){ for (int index = 1; index < n; index++){ int tmp = array[index]; int leftIndex = index - 1; while (leftIndex >= 0 && array[leftIndex] > tmp){//比较 array[leftIndex + 1] = array[leftIndex];//移动 leftIndex--; } array[leftIndex + 1] = tmp;//插入 } } //测试 public static void main(String[] args) { int[] array = {4,8,6,85,2,4,5,98}; insertionSort(array,array.length); Util.ptingArray(array); } }