快速排序(Java)实现

原创
2020/06/24 08:39
阅读数 52

实现原理

假设有一个需要排序的序列S, 快速排序利用简单的分治法对序列S进行排序, 将S分解成子序列,递归的对每一个子序列进行排序,然后通过简单的连接把每个子序列再连接起来.
如何划分

首先确保S中至少有两个元素(不然没法排的嗷铁汁). 从S中先择一个轴元素(privot),假设有三个序列L,E,R.
L放比轴元素小的元素,E放于轴元素相等的元素, R放比轴元素大的元素.
然后递归的对L和R进行排序.
时间复杂度

最坏的情况是O(nn), 当输入序列为有序的情况
最好的情况是O(nlogn),此时L和R的大小大致相等.每个内部节点储存一个轴元素,并调用其大小相等的两个子节点.以此类推,根有一个轴元素,第一层有两个轴元素,第二层有2平方个轴元素…(你以为你在第二层,我在第一层,其实我在第五层)

 

 

 public static void quickSort(int[] arr, int low, int high) {
       
        if (low > high) {
            return;
        }
        int pivot = arr[low];//轴元素
        int i = low;
        int j = high;
        //
        while (j > i) {
            while (pivot <= arr[j] && i < j) {//从右开始,向左查找,找比arr[low]小的
                j--;
            }

            while (arr[i] <= pivot && i < j && i < j) {//从左向右找比arr[low]大的
                i++;
            }
            if (i < j) {//找的的话调换位置
               int temp1 = 0;
                temp1 = arr[j];
                arr[j] = arr[i];
                arr[i] = temp1;

            }
            if (i == j) {//轴元素放在正确的位置
                int temp2 = arr[low];
                arr[low] = arr[i];
                arr[i] = temp2;


            }

        }
        if (low < i - 1) {递归
            quickSort(arr, low, i - 1);
            quickSort(arr, i + 1, high);
        }

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部