Java|【数据结构与算法】——必知必会的排序算法你会几种

作者简介:大家好,我是IT界的小学生——郭嘉烨
博客主页:郭嘉烨的CSDN博客主页
您的点赞评论,支持是我创作的最大动力!!!
常用的几个排序算法
1.冒泡排序
2.选择排序
3.插入排序
4.希尔排序
5.归并排序
【Java|【数据结构与算法】——必知必会的排序算法你会几种】6.快速排序

1.冒泡排序 算法原理:
  • 从第一个元素开始,比较相邻的两个元素,如果第一个大于第二个,则交换它们
  • 对每一对相邻的元素做相同的操作,从第一对到最后一对,最终最后一位元素就是最大值
  • 对每一个元素重复上述步骤,最后一个除外
动图演示:
Java|【数据结构与算法】——必知必会的排序算法你会几种
文章图片


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|【数据结构与算法】——必知必会的排序算法你会几种
文章图片



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|【数据结构与算法】——必知必会的排序算法你会几种
文章图片


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|【数据结构与算法】——必知必会的排序算法你会几种
文章图片

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 = 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|【数据结构与算法】——必知必会的排序算法你会几种
文章图片




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|【数据结构与算法】——必知必会的排序算法你会几种
文章图片


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}



    推荐阅读