常用的几个排序算法
1.冒泡排序
算法原理：
- 从第一个元素开始，比较相邻的两个元素，如果第一个大于第二个，则交换它们
- 对每一对相邻的元素做相同的操作，从第一对到最后一对，最终最后一位元素就是最大值
- 对每一个元素重复上述步骤，最后一个除外
动图演示：
编辑
java实现代码：
public class Bubble { //数组排序 public static void sort(Comparable[] a){ for (int i = a.length - 1;i > 0;i--){ for (int j = 0;j < i;j++){ if (greater(a[j],a[j + 1])){ swap(a,j,j + 1); } } } } //比较 v 是否大于 w public static boolean greater(Comparable v,Comparable w){ return v.compareTo(w) > 0; } //数组元素交换位置 private static void swap(Comparable[] a,int i,int j){ Comparable temp; temp = a[i]; a[i] = a[j]; a[j] = temp; } }
public class BubbleTest { public static void main(String[] args) { Integer[] arr = {3,5,9,7,2,1}; Bubble.sort(arr); System.out.println(Arrays.toString(arr)); } } //排序前：{3,5,9,7,2,1} //排序后：{1,2,3,5,7,9}
2.选择排序
算法原理：
- 每次从待排序的数据元素中选择最小值或最大值，放在第一位
- 从剩余的元素中继续寻找最小或最大元素，放在已排序元素的后面
- 重复以上步骤，直到排序完成
动图演示：
编辑
java代码实现：
public class SelectionSort { // 选择排序 public static void sort(Comparable[] a){ for (int i = 0;i <= a.length - 2;i++){ //定义一个变量，记录最小元素的索引 int minIndex = i; for (int j = i + 1;j < a.length;j++){ //比minIndex与j两个索引处的值的大小 if (greater(a[minIndex],a[j])){ minIndex = j; } } //交换最小元素的所在索引minIndex处的值与索引值为i的元素的值 swap(a,i,minIndex); } } //比较 v 是否大于 w public static boolean greater(Comparable v,Comparable w){ return v.compareTo(w) > 0; } //数组元素交换位置 private static void swap(Comparable[] a,int i,int j){ Comparable temp; temp = a[i]; a[i] = a[j]; a[j] = temp; } }
public class SelectionSortTest { public static void main(String[] args) { Integer[] arr = {9,18,38,2,46,8,43,46,5,12}; SelectionSort.sort(arr); System.out.println(Arrays.toString(arr)); } } //排序前：{9,18,38,2,46,8,43,46,5,12} //排序后：{2,5,8,9,12,18,38,43,46,46}
3.插入排序
算法原理：
- 把所有元素分为两个序列，将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
- 从未排序序列中的第一个元素开始，向已排序的序列中插入
- 倒序遍历已排序序列，依次和待插入的元素比较，找到一个小于或等于待插入的元素，插入到该元素后面，其余元素向后移动一位
动图演示：
编辑
java代码实现
public class InsertionSort { // 插入排序 public static void sort(Comparable[] a){ for (int i = 1;i < a.length;i++){ for (int j = i;j > 0;j--){ //比较索引j处的值与索引j-1处的值,如果j-1索引处的值大，则交换数据，反之，则找到了合适的位置，退出循环 if (greater(a[j - 1],a[j])){ swap(a,j - 1,j); }else{ break; } } } } //比较 v 是否大于 w public static boolean greater(Comparable v,Comparable w){ return v.compareTo(w) > 0; } //数组元素交换位置 private static void swap(Comparable[] a,int i,int j){ Comparable temp; temp = a[i]; a[i] = a[j]; a[j] = temp; } }
public class InsertionSortTest { public static void main(String[] args) { Integer[] arr = {3,44,38,5,47,15,36,26,27}; InsertionSort.sort(arr); System.out.println(Arrays.toString(arr)); } } //排序前：{3,44,38,5,47,15,36,26,27} //排序后：{3,5,15,26,27,36,38,44,47}
4.希尔排序
算法原理：
- 选择一个增长量h，按照增长量h作为数据分组的依据对数据分组
- 对分好的每一组完成插入排序
- 减小增长量，最小减为一，重复第二步
动图演示：
编辑
java代码实现：
public class ShellSort { //希尔排序 public static void sort(Comparable[] a){ int h = 1; while (h < a.length / 2){ h = 2 * h + 1; } while (h >= 1){ //找到待插入的元素 for (int i = h;i <a.length;i++){ //把待插入的元素插入 for (int j = i; j >= h; j-=h) { if (greater(a[j - h],a[j])){ swap(a,j - h,j); }else{ break; } } } //减小h的值 h = h / 2; } } //比较 v 是否大于 w public static boolean greater(Comparable v,Comparable w){ return v.compareTo(w) > 0; } //数组元素交换位置 private static void swap(Comparable[] a,int i,int j){ Comparable temp; temp = a[i]; a[i] = a[j]; a[j] = temp; } }
public class ShellSortTest { public static void main(String[] args) { Integer[] arr = {86,11,54,34,53,12,45,81,19,65}; ShellSort.sort(arr); System.out.println(Arrays.toString(arr)); } } //排序前：{86,11,54,34,53,12,45,81,19,65} //排序后：{11,12,19,34,45,53,54,65,81,86}
5.归并排序
算法原理：
- 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
- 设定两个指针，最初位置分别为两个已经排序序列的起始位置
- 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
- 重复步骤c直到某一指针超出序列尾
- 将另一序列剩下的所有元素直接复制到合并序列尾
动图演示：
编辑
java代码实现：
public class MergeSort { //归并所需的辅助数组 private static Comparable[] assist; //比较 v 是否小于 w public static boolean less(Comparable v,Comparable w){ return v.compareTo(w) < 0; } //数组元素交换位置 private static void swap(Comparable[] a,int i,int j){ Comparable temp; temp = a[i]; a[i] = a[j]; a[j] = temp; } //排序 public static void sort(Comparable[] a){ //初始化辅助数组 assist = new Comparable[a.length]; int l = 0; int h = a.length - 1; sort(a,l,h); } private static void sort(Comparable[] a,int l,int h){ if (h <= l){ return; } //分组 int mid = l +(h - l) / 2; //分别对每组数据排序 sort(a,l,mid); sort(a,mid + 1,h); //对数组进行归并 merge(a,l,mid,h); } //对数组进行归并 private static void merge(Comparable[] a,int l,int mid,int h){ //定义三个指针 int i = l; int p1 = l; int p2 = mid + 1; //遍历，移动p1,p2指针，比较两处索引的值,小的放到辅助数组的对应索引处 while (p1 <= mid && p2 <=h){ if (less(a[p1],a[p2])){ assist[i++] = a[p1++]; }else { assist[i++] = a[p2++]; } } //遍历数组，如果p1的指针没有走完，则顺序移动p1指针，把对应的元素放到辅助数组的对应索引处 while (p1 <= mid){ assist[i++] = a[p1++]; } //遍历数组，如果p2的指针没有走完，则顺序移动p2指针，把对应的元素放到辅助数组的对应索引处 while (p2 <= h){ assist[i++] = a[p2++]; } //把辅助数组中的元素拷贝到原数组中 for (int j = l; j <= h; j++) { a[j] = assist[j]; } } }
public class MergeSortTest { public static void main(String[] args) { Integer[] arr = {5,6,3,1,8,7,2,4}; MergeSort.sort(arr); System.out.println(Arrays.toString(arr)); } } //排序前：{5,6,3,1,8,7,2,4} //排序后：{1,2,3,4,5,6,7,8}
6.快速排序
算法原理：
- 从数列中挑出一个元素作为基准点
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面
- 然后基准值左右两边，重复上述步骤
- 通过递归把基准值元素左右两侧的数组排序，排完之后，整个数组就排序完成了
动图演示：
编辑
java代码实现：
public class QuickSort { //比较 v 是否小于 w public static boolean less(Comparable v,Comparable w){ return v.compareTo(w) < 0; } //数组元素交换位置 private static void swap(Comparable[] a,int i,int j){ Comparable temp; temp = a[i]; a[i] = a[j]; a[j] = temp; } //排序 public static void sort(Comparable[] a){ int l = 0; int h = a.length - 1; sort(a,l,h); } private static void sort(Comparable[] a,int l,int h){ if (h <= l) return; //对数组进行分组(左右两个数组) // i 表示分组之后基准值的索引 int i = partition(a, l, h); //让左边的数组有序 sort(a,l,i - 1); //让有边的数组有序 sort(a,i + 1,h); } public static int partition(Comparable[] a,int l,int h){ //确定基准值 Comparable key = a[l]; //定义两个指针 int left = l; int right = h + 1; //切分 while (true){ //从右向左扫描，移动right指针找一个比基准值小的元素，找到就停止 while (less(key,a[--right])){ if (right == l) break; } //从左向右扫描，移动left指针找一个比基准值大的元素，找到就停止 while (less(a[++left],key)){ if (left == h) break; } if (left>=right){ break; }else { swap(a,left,right); } } //交换基准值 swap(a,l,right); return right; } }
public class QuickSortTest { public static void main(String[] args) { Integer[] arr = {3,1,2,4,9,6}; QuickSort.sort(arr); System.out.println(Arrays.toString(arr)); } } //排序前：{3,1,2,4,9,6} //排序后：{1,2,3,4,6,9}
