小饶学编程之JAVA SE第一部分——快速排序算法

喜欢ヅ旅行 2022-12-19 06:04 133阅读 0赞

### 快速排序算法 ###

*  一、算法描述
 *  二、算法原理
 *  三、时间复杂度
 *  四、算法实现

# 一、算法描述 #

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

# 二、算法原理 #

*  (1)首先设定一个分界值，通过该分界值将数组分成左右两部分。
 *  (2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。
 *  (3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
 *  (4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

# 三、时间复杂度 #

快速排序的一次划分算法从两头交替搜索，直到low和hight重合，因此其时间复杂度是O(n)；而整个快速排序算法的时间复杂度与划分的趟数有关。  
理想的情况是，每次划分所选择的中间数恰好将当前序列几乎等分，经过log2n趟划分，便可得到长度为1的子表。这样，整个算法的时间复杂度为O(nlog2n)。  
最坏的情况是，每次所选的中间数是当前序列中的最大或最小元素，这使得每次划分所得的子表中一个为空表，另一子表的长度为原表的长度-1。这样，长度为n的数据表的快速排序需要经过n趟划分，使得整个排序算法的时间复杂度为O(n2)。

# 四、算法实现 #

public static int[] qsort(int arr[],int start,int end) {
                
        int pivot = arr[start];        
        int i = start;        
        int j = end;        
        while (i<j) {
                    
            while ((i<j)&&(arr[j]>pivot)) {
                        
                j--;            
            }            
            while ((i<j)&&(arr[i]<pivot)) {
                        
                i++;            
            }            
            if ((arr[i]==arr[j])&&(i<j)) {
                        
                i++;            
            } else {
                        
                int temp = arr[i];                
                arr[i] = arr[j];                
                arr[j] = temp;            
            }        
        }        
        if (i-1>start) arr=qsort(arr,start,i-1);        
        if (j+1<end) arr=qsort(arr,j+1,end);        
        return (arr);    
    }    
     
    public static void main(String[] args) {
                
        int arr[] = new int[]{
        3,3,3,7,9,122344,4656,34,34,4656,5,6,7,8,9,343,57765,23,12321};        
        int len = arr.length-1;        
        arr=qsort(arr,0,len);        
        for (int i:arr) {
                    
            System.out.print(i+"\t");        
        }    
    }