1、选择排序 1.1、选择排序思路 选择排序( select sorting)也是一种简单的排序方法。
它的基本思想是:第一次从arr[0]
到arr[n-1]
中选取最小值,与arr[0]
交换,第二次从arr[1]
到arr[n - 1]
中选取最小值,与arr[1]
交换,第三次从arr[2]
到arr[n-1]
中选取最小值,与arr[2]
交换,…,第 i 次从arr[i-1]
到arr[n-1]
中选取最小值与arr[i-1]
交换,…,第n-1次从arr[n-2]
到arr[n-1]
中选取最小值,与arr[n-2]
交换,总共通过n-1次,得到一个按排序码从小到大排列的有序序列。
1.2、思路分析图
1.3、代码实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 public static void selectSort (int [] arr) { for (int i = 0 ; i < arr.length - 1 ; i++) { int minIndex = i; int minValue = arr[i]; for (int j = i + 1 ; j < arr.length; j++) { if (arr[j] < minValue) { minValue = arr[j]; minIndex = j; } } if (minIndex != i) { arr[minIndex] = arr[i]; arr[i] = minValue; } } }
1.4、测试 在main方法中创建一个数组,使用选择排序进行排序
1 2 3 int [] arr = {101 ,88 ,777 ,1 ,-100 ,108 };selectSort(arr); System.out.println(Arrays.toString(arr));
排序结果如下
2、插入排序 2.1、插入排序算法介绍 插入排序属于内部排序法,是对要排序的元素以插入的方式找寻该元素的适当位置,以达到排序的目的
2.2、基本思想 插入排序的基本思想是:把n个待排序元素看为一个有序表和一个无序表,开始时有序表中只包含一个元素,无序表中有 n - 1 个元素 ,排序过程中每次从无序表中取出第一个元素,把它的排序码依次与有序表元素的排序码进行比较,然后把它插入到有序表的适当位置,使之成为新的有序表
2.3、思路图
2.4、代码实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 public static void insertSort (int [] arr) { for (int i = 1 ; i < arr.length; i++) { int insertVal = arr[i]; int insertIndex = i - 1 ; while (insertIndex >= 0 && insertVal < arr[insertIndex]) { arr[insertIndex + 1 ] = arr[insertIndex]; insertIndex--; } arr[insertIndex + 1 ] = insertVal; } }
3、快速排序 3.1、介绍 快速排序(Quick sort)是对冒泡排序的一种改进;
基本思想是:通过一趟排序将要排序的数据分割为独立的两部分,其中一部分的所有数据都比另一部分的所有数据要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据都变为有序序列。
3.2、示意图
3.3、代码实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 public static void quickSort (int [] arr, int left, int right) { int l = left; int r = right; int temp = 0 ; int pivot = arr[(left + right) / 2 ]; while (l < r) { while (arr[l] < pivot) { l += 1 ; } while (arr[r] > pivot) { r -= 1 ; } if (l >= r) { break ; } temp = arr[l]; arr[l] = arr[r]; arr[r] = temp; if (arr[l] == pivot) { r -= 1 ; } if (arr[r] == pivot) { l += 1 ; } } if (l == r) { l += 1 ; r -= 1 ; } if (left < r) { quickSort(arr,left,r); } if (right > l) { quickSort(arr,l,right); } }
数据结构与算法学习(九)-选择排序、插入排序与快速排序