个人中心
gpt4 book ai didi

快速排序和分治排序介绍

转载 作者：qq735679552 更新时间：2022-09-29 22:32:09 24 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章快速排序和分治排序介绍由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

快速排序让我看了很久，也折磨了我很长时间，因为大体上的思路我是有了，但是写代码时总是出现各种问题，要想把它调试出来对我个人来说还是有一定难度的，而且因为工作和偷懒的原因，导致之前调试不出来的错误放了很久，今天终于出来啦，还是有些小激动的哦，下面来分享一下我的代码并做一点点说明.

　　要学会快速排序，就必须先要学会分治法，分治的思想是给一串乱序的数字（数字是假设，也可以是其他的对象，当然方法的参数可以自己定义哦，我在这里假设有一个整型的数组吧）然后给他一个中间数，分治法会把这些数字以给他的那个是中间数为分界分为两部分，一部分在中间数的左边，另一部分在右边，以这个数为分界点，两边的数现在还是乱序的，我给他定义的方法如下:

?
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
//left是数组的想分治部分的左端点，right是数组分治部分的总端点，如长度为10的数组，我想对前5个整数进行分治，则传0，4即可
   public int signalFenZhi( int left, int right){
     if (left< 0 ||left>n- 1 ||right< 0 ||right>n- 1 ){
       return - 1 ;
     }
     int temp = test[left];
     int j=right;
     int i=left;
    
     while (i<j){
       while (test[j]>=test[left]&&i<j){
         j--;
       }
       while (test[i]<=test[left]&&i<j){
         i++;
       }
      
       if (i<j){
         temp = test[i];
         test[i]=test[j];
         test[j]=temp;
       }
     }
    
     if (i==j){
       temp = test[i];
       test[i]=test[left];
       test[left]=temp;
     }
    
     for ( int m= 0 ;m<n;m++){
       System.out.print(test[m]+ "   " );
     }
    
     return i;
      
   }

当然，也可以把那个中间数当参数传进来，现在我只是单纯的以数组的传进来的第left数做为分界数，这只是为了说明.

　　明白了分治，那么快速排序也就简单了，那就是对已经分为两部分的数再进行分治，依次类推，直到全部的数字都有序为止，代码如下:

?
1
2
3
4
5
6
7
8
9
10
11
12
public void quickSort( int left, int right){
     if (right-left< 1 ){
       return ;
     } else {
       int point = this .signalFenZhi(left, right);
       System.out.println(point);
       //if(point!=left&&point!=right){
         quickSort(left,point- 1 );
         quickSort(point+ 1 ,right);
       //}
     }
   }

快速排序的效率在众多的排序算法中是很优秀的，时间复杂度为O(N*log2n),但是如果分治的分界点选的不好的话，时间复杂度将会降到（n的平方）,因为如果正好这个数组是有序的，然后我们每次都取传过来的最左端的数，那么效率就会很低，所以要避免发生这种情况，如果检测所有的选项，那么将会很花时间，所以一个折中的办法 ，就是把最左端的数和最右端的数加上一个中间的数，找到他们三个中间的数，以这个为分界值就会变的好一点，在上面方法的基础上，修改以后的代码如下，但是我做完了以后这样的做法不是很好，应该把分界值也当做传给分治的方法会好些，细心的朋友可以自己试一下，我在这里就不试了哈，大体上是一样的哦！ 。

?
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
package com.jll;
 
public class FenZhi {
  
   int [] test;
  
   int n= 10 ;
  
   public FenZhi(){
     test = new int [ 10 ];
    
     for ( int i= 0 ;i<n;i++){
       test[i]=( int )(Math.random()* 100 )+ 1 ;
       System.out.print(test[i]+ "   " );
     }
     System.out.println();
   }
  
   public FenZhi( int n){
     if (n> 0 ){
       this .n=n;
       test = new int [n];
      
       for ( int i= 0 ;i<n;i++){
         test[i]=( int )(Math.random()* 100 )+ 1 ;
       }
     }
   }
  
   public int signalFenZhiMajorizationFirst( int left, int right){
     if (left< 0 ||left>n- 1 ||right< 0 ||right>n- 1 ||left>=right){
       return - 1 ;
     }
    
     if (right-left>= 2 ){
       int middle = (right+left)/ 2 ;
       if (test[left]>test[middle]){
         int temp = test[middle];
         test[middle] = test[left];
         test[left] = temp;
       }
       if (test[left]>test[right]){
         int temp = test[left];
         test[left] = test[right];
         test[right] = temp;
       }
       if (test[middle]>test[right]){
         int temp = test[middle];
         test[middle] = test[right];
         test[right] = temp;
       }
       int temp = test[middle];
       test[middle] = test[left];
       test[left] = temp;
       int j=right- 1 ;
       int i=left+ 1 ;
      
       while (i<j){
         while (test[j]>=test[left]&&i<j){
           j--;
         }
         while (test[i]<=test[left]&&i<j){
           i++;
         }
        
         if (i<j){
           temp = test[i];
           test[i]=test[j];
           test[j]=temp;
         }
       }
       if (i==j){
         temp = test[i];
         test[i]=test[left];
         test[left]=temp;
       }
      
       /*if(i==j){
         temp = test[middle];
         test[middle]=test[i];
         test[i]=temp;
       }*/
      
       /*for(int m=0;m<n;m++){
         System.out.print(test[m]+"   ");
       }*/
      
       return i;
     } else {
       if (test[right]<test[left]){
         int temp = test[right];
         test[right] = test[left];
         test[left] = temp;
       }
       return right;
     }
   }
  
   public void quickSortMajorizationFirst( int left, int right){
     if (right-left< 1 ){
       return ;
     } else {
       int point = this .signalFenZhiMajorizationFirst(left, right);
       System.out.println( "the point is:" +point);
       quickSortMajorizationFirst(left,point- 1 );
       quickSortMajorizationFirst(point+ 1 ,right);
     }
   }
  
   public static void main(String[] args) {
     FenZhi f = new FenZhi();
     System.out.println(f.signalFenZhiMajorizationFirst( 0 , 9 ));
     System.out.println();
     f.quickSortMajorizationFirst( 0 ,f.n- 1 );
    
     //f.quickSort(0,f.test.length-1);
     for ( int i:f.test){
       System.out.print(i+ " " );
     }
   }
}

代码运行如下:

?
1
2
3
4
5
6
7
8
9
10
95   40   64   18   78   23   73   84   40  
 
 
the point is: 4
the point is: 1
the point is: 3
the point is: 7
the point is: 6
the point is: 9
18 23 40 40 64 73 78 84 95

以上就是我学习到的东西，记录一下，以备后面查阅.

最后此篇关于快速排序和分治排序介绍的文章就讲到这里了,如果你想了解更多关于快速排序和分治排序介绍的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

24 4 0
文章推荐： java高级排序之希尔排序
文章推荐： 单例模式 分析代码优化方法
文章推荐： Java中使用synchronized关键字实现简单同步操作示例
文章推荐： Java中使用opencsv读写csv文件示例
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com