java排序算法图文详解

时间:2022-09-06 12:31:04

一、直接插入排序

基本思想:

将一个记录插入到已排序的有序表中,使插入后的表仍然有序

对初始关键字{49 38 65 97 76 13 27 49}进行直接插入排序

java排序算法图文详解

  1. package Sort;
  2. //插入排序
  3. public class InsertSort {
  4. public static void main(String[] args) {
  5. int [] arr={49,38,65,97,76,13,27,49};
  6. sort(arr);
  7. print(arr);
  8. }
  9. private static void sort(int [] arr) {
  10. for (int i = 1; i < arr.length; i++) {
  11. for(int j=i;j>0;j--){
  12. if(arr[j]<arr[j-1]){
  13. swap(arr,j,j-1);
  14. }
  15. }
  16. }
  17. }
  18. private static void swap(int [] arr,int i,int j){
  19. int temp=0;
  20. temp=arr[i];
  21. arr[i]=arr[j];
  22. arr[j]=temp;
  23. }
  24. private static void print(int [] arr) {
  25. for (int i = 0; i <arr.length ; i++) {
  26. System.out.print(arr[i]+" ");
  27. }
  28. }
  29. }

13 27 38 49 49 65 76 97

Process finished with exit code 0

二、 希尔排序

希尔排序又称“缩小增量排序”(Diminishing Increment Sort))属于插入排序类。

基本思想:

先将整个待排序的记录分割成若干子序列分别进行“直接插入排序”,待整个序列中的记录”基本有序“时,再对全体记录进行一次直接插入排序。

java排序算法图文详解

  1. package Sort;
  2. //希尔排序是插入排序的改良
  3. public class ShellSort {
  4. public static void main(String[] args) {
  5. int [] arr={16,25,12,30,47,11,23,36,9,18,31};
  6. sort(arr);
  7. print(arr);
  8. }
  9. private static void sort(int [] arr) {
  10. //gap设置优化
  11. int h=1;
  12. while(h<arr.length/3){
  13. h=h*3+1;
  14. }
  15. for(int gap=h;gap>0;gap=(gap-1)/3) {//gap:希尔排序的间距
  16. for (int i = gap; i < arr.length; i++) {
  17. for (int j = i; j >gap-1; j-=gap) {
  18. if (arr[j] < arr[j - gap]) {
  19. swap(arr, j, j - gap);
  20. }
  21. }
  22. }
  23. }
  24. }
  25. private static void swap(int [] arr,int i,int j){
  26. int temp=0;
  27. temp=arr[i];
  28. arr[i]=arr[j];
  29. arr[j]=temp;
  30. }
  31. private static void print(int [] arr) {
  32. for (int i = 0; i <arr.length ; i++) {
  33. System.out.print(arr[i]+" ");
  34. }
  35. }
  36. }

9 11 12 16 18 23 25 30 31 36 47

Process finished with exit code 0

三、冒泡排序

冒泡排序

四、快速排序

对冒泡排序的一种改进

基本思想:

通过一趟排序将待排序记录分割成独立的两部分,其中一部分的关键字均比另一部分的关键字小,则可分别对这两部分记录继续分别进行排序,以达到整个序列有序。

java排序算法图文详解

java排序算法图文详解

  1. package Sort;
  2. import java.util.Arrays;
  3. //快速排序
  4. public class QuickSort {
  5. public static void main(String[] args) {
  6. int[] arr={49,38,65,97,76,13,27,49};
  7. sort(arr,0,arr.length-1);
  8. System.out.println(Arrays.toString(arr));
  9. }
  10. private static void sort(int [] arr,int start,int end) {
  11. if(start<end){
  12. //把数组的第0个数作为标准数
  13. int stared=arr[start];
  14. //记录要排序的下标
  15. int low=start;
  16. int height=end;
  17. //循环找出比标准数大和比标准数小的数
  18. while(low<height){
  19. //右边数字比标准数大
  20. while(low<height&&stared<=arr[height]){
  21. height--;
  22. }
  23. //用右边的数字替换左边的数字
  24. arr[low]=arr[height];
  25. //左边数字比标准数小
  26. while(low<height&&stared>=arr[low]){
  27. low++;
  28. }
  29. //用左边的数字替换右边的数字
  30. arr[height]=arr[low];
  31. }
  32. arr[low]=stared;
  33. sort(arr,start,low);
  34. sort(arr,low+1,height);
  35. }
  36. }
  37. }

[13, 27, 38, 49, 76, 97, 65, 49]

Process finished with exit code 0

五、选择排序(Selection Sort)

选择排序

六、堆排序

  1. 堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复杂度均为O(nlogn),它也是不稳定排序。

堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆, 注意 : 没有要求结点的左孩子的值和右孩子的值的大小关系。

每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆

1、大顶堆举例说明:

java排序算法图文详解

我们对堆中的结点按层进行编号,映射到数组中就是下面这个样子:

java排序算法图文详解

大顶堆特点:arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2] // i 对应第几个节点,i从0开始编号

2、小顶堆举例说明

java排序算法图文详解

小顶堆:arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2] // i 对应第几个节点,i从0开始编号

一般升序采用大顶堆,降序采用小顶堆

堆排序基本思想

一、堆排序的基本思想是:

将待排序序列构造成一个大顶堆

此时,整个序列的最大值就是堆顶的根节点。

将其与末尾元素进行交换,此时末尾就为最大值。

然后将剩余n-1个元素重新构造成一个堆,这样会得到n个元素的次小值。如此反复执行,便能得到一个有序序列了。

二、代码示例

  1. package Sort;
  2. import java.util.Arrays;
  3. /**构造大顶堆
  4. * 1、原顺序二叉树 非叶子节点在数组中的索引i=1时;arr[i]=6 i=0时
  5. * 4 i的右节点值比它大,交换得 : 9
  6. * /\ 4 /\
  7. * 6 8 /\ 6 8
  8. * /\ 9 8 /\
  9. * 5 9 /\ 5 4
  10. * 5 6
  11. */
  12.  
  13. public class HeapSort {
  14. public static void main(String[] args) {
  15. int [] arr={4,6,8,5,9};
  16. heapSort(arr);
  17. }
  18. //编写一个堆排序的方法
  19. public static void heapSort(int[] arr){
  20. int temp=0;
  21. for(int i=arr.length/2-1;i>=0;i--){
  22. adjustHeap(arr,i,arr.length);
  23. }
  24. //将堆顶元素与末尾元素进行交换,此时末尾就为最大值,将最大值全放在数组最后
  25. //重新调整结构,使其满足堆定义,继续交换堆顶元素与当前末尾元素,反复执行调整交换步骤,使整个序列达到有序
  26. for(int j=arr.length-1;j>0;j--) {
  27. //交换
  28. temp = arr[j];
  29. arr[j] = arr[0];
  30. arr[0] = temp;
  31. adjustHeap(arr, 0, j);
  32. }
  33. System.out.println("数组"+Arrays.toString(arr));
  34. }
  35. //将数组调整为一个大顶堆
  36. /**
  37. * 功能:完成将以i对应的非叶子节点的树调整成大顶堆
  38. * 举例:int[]arr={4,6,8,5,9};=>i=1=>adjustHeap=>得到{4,9,8,5,6}
  39. * 如果再次调整adjustHeap传入i=0,{4,9,8,5,6}=>得到{9,6,8,5,4}
  40. * @param arr 表示要调整的数组
  41. * @param i 表示非叶子节点在数组中的索引
  42. * @param length 表示对多少个元素进行调整,length在逐渐减少
  43. */
  44. public static void adjustHeap(int[]arr,int i,int length){
  45. int temp=arr[i];//先取出当前元素的值,保存在临时变量中
  46. //开始调整
  47. //k=i*2+1;k是i节点的左子节点
  48. for(int k=i*2+1;k<length;k=k*2+1){
  49. if(k+1<length&&arr[k]<arr[k+1]){//说明左子节点的值小于右子节点的值
  50. k++;//k指向右子节点
  51. }
  52. if(arr[k]>temp){//如果子节点大于父节点
  53. arr[i]=arr[k];//把较大的值赋给当前节点
  54. i=k;//!!!i指向k,继续循环比较
  55. }else{
  56. break;
  57. }
  58. }
  59. //当for循环结束后,已经将以i为父结点的最大值放在了堆顶上(局部)
  60. arr[i]=temp;//将temp的值放在调整后的位置
  61. }
  62. }

堆排序结果:

数组[4, 5, 6, 8, 9]

七、归并排序

定义:

又一类不同的排序方法,将两个或两个以上的有序表合并成一个新的有序表。

需要辅助空间:O(n)

整个归并需要 [log2n]

时间复杂度:O(nlog2n)

缺点:归并排序占用附加存储较多, 需要另外一个与原待排序对象数组同样大小的辅助数组。

优点:归并排序是一个稳定的排序方法

思路可以推广到“多路归并”

常用于外部排序

java排序算法图文详解

java排序算法图文详解

  1. package Sort;
  2. //归并排序
  3. public class MergeSort {
  4. public static void main(String[] args) {
  5. int [] arr={4,5,7,8,1,2,3,6};
  6. sort(arr);
  7. print(arr);
  8. }
  9. private static void sort(int [] arr) {
  10. int mid=arr.length/2;
  11. int[]temp=new int[arr.length];
  12. int i=0;//标记左边数组
  13. int j=mid+1;//标记右边数组起始点
  14. int k=0;
  15. while(i<=mid&&j<arr.length){
  16. if(arr[i]<=arr[j]){
  17. temp[k]=arr[i];
  18. i++;
  19. k++;
  20. }else{
  21. temp[k]=arr[j];
  22. j++;
  23. k++;
  24. }
  25. }
  26. while(i<=mid){temp[k++]=arr[i++];}//将左边剩余的,复制到数组
  27. while(j<arr.length){temp[k++]=arr[j++];}//将右边剩余的,复制到数组
  28. }
  29.  
  30. private static void print(int [] arr) {
  31. for (int i = 0; i <arr.length ; i++) {
  32. System.out.print(arr[i]+" ");
  33. }
  34. }
  35. }

1 2 3 4 5 6 7 8

Process finished with exit code 0

总结

本篇文章就到这里了,希望可以给你带来一些帮助,也希望您能够多多关注我们的更多内容!

原文链接:https://blog.csdn.net/weixin_55782195/article/details/117897740