选择排序:每次循环找出最小值的索引,直接进行交换。
n表示数组长度 , end 表示最后一次循环。 第1次循环: 在 0 ~ n-1 中找出最小值 ,放在索引为0的位置。 第2次循环: 在 1 ~ n-1 中找出最小值 ,放在索引为1的位置。 第3次循环: 在 2 ~ n-1 中找出最小值 ,放在索引为2的位置。 第4次循环: 在 3 ~ n-1 中找出最小值 ,放在索引为3的位置。 .... 第n-1次循环: 在 n-2 ~ n-1 中找出最小值 ,放在索引为n-1的位置。 即 每次循环找出最小值直接交换两个元素的位置。1.2 冒泡排序分析
冒泡排序:每次循环,两两比较,找出最大值,放在最后。
第1次循环:从 0 ~ n-1 范围中 找到最大值,放在n-1位置。 第2次循环:从 0 ~ n-2 范围中 找到最大值,放在n-2位置。 第3次循环:从 0 ~ n-3 范围中 找到最大值,放在n-3位置。 ...... 第n-1次循环:从 0 ~ 1 范围中 找到最大值,放在1位置。 即:两两比较,每次循环找出最大值,放在最后。1.3 插入排序分析
第1次循环:从 0 ~ 1 范围中排序 第2次循环:从 0 ~ 2 范围中排序 第3次循环:从 0 ~ 3 范围中排序 ...... 第n-1次循环:从 0 ~ n-1 范围中排序 即:每次循环,将待排序的值和之前有序的元素进行比较,放在合适的位置。二、代码实现
public class SortCode { public static void main(String[] args) { int[] arr = {9, 4, 1, 6, 2, 5, 4,1}; pringArray(arr); // selectSort(arr); // bubbleSort1(arr); // bubbleSort2(arr); // insertionSort1(arr); insertionSort2(arr); pringArray(arr); } public static void pringArray(int[] arr){ for (int i = 0; i < arr.length; i++) { System.out.print(arr[i]+" "); } System.out.println(); } public static void swap(int[] arr,int i,int j){ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } public static void selectSort(int[] arr){ if (arr == null || arr.length < 2 ){ return; } int num = 0 ; int N = arr.length; for (int i = 0; i < N; i++) { int minValueIndex = i; //注意:内层循环的初始值是当前值的下一位,即i+1,因为内层循环为当前值和后面的值比较,并记录最小值的位置 for (int j = i+1; j < N; j++) { // 2,1,6,8,1,5 // 0 1 2 3 4 5 minValueIndex = arr[minValueIndex] > arr[j] ? j:minValueIndex; num ++; } swap(arr,minValueIndex,i); } System.out.println(num); } public static void bubbleSort1(int[] arr){ if (arr == null || arr.length < 2){ return; } int num = 0 ; int N = arr.length; // 0 ~ n-1 // 0 ~ n-2 // 0 ~ n-3 //外层循环控制次数 for (int i = 0; i < N; i++) { //内层循环进行两两比较,从索引0位置开始两两比较 即:j和j+1进行比较,j++,此处 限制条件:j < N-1 和j < N-1-i 效果是一样的。 for (int j = 0; j < N-1; j++) { if (arr[j] > arr[j+1]){ swap(arr,j+1,j); num ++; } } } System.out.println(num); } public static void bubbleSort2(int[] arr){ if (arr == null || arr.length < 2){ return; } int num = 0 ; int N = arr.length; for (int end = N-1; end >= 0; end--) { for (int second = 1; second <= end ; second++) { if (arr[second-1] > arr[second]){ swap(arr,second-1,second); num ++; } } } System.out.println(num); } public static void insertionSort1(int[] arr){ if (arr == null || arr.length < 2){ return; } int N = arr.length; int num = 0; for (int i = 0; i < N; i++) { int nextValueIndex = i ; while ((nextValueIndex -1)>=0 && (arr[nextValueIndex] < arr[nextValueIndex-1])){ swap(arr,nextValueIndex,nextValueIndex-1); nextValueIndex--; num ++; } } System.out.println(num); } public static void insertionSort2(int[] arr){ if (arr == null || arr.length < 2){ return; } int N = arr.length; int num = 0 ; for (int end = 1; end < N; end++) { for (int pre = end -1 ; pre >= 0 &&(arr[pre] > arr[pre+1]); pre--) { swap(arr,pre,pre+1); num++; } } System.out.println(num); } }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)