排序算法整理

Posted by Lain on 09-25,2019

排序算法整理

0

1、快速排序

快速排序基于分治思想,相比于冒泡排序中每一轮只将一个元素移动到最右边,快速排序每轮会选出一个基准元素,并将数组中比他大的数移动到右边(从小到大排序),比它小的数移动到左边,从而将元素分割成两个部分,下一轮再分别在这两部分进行同样的操作。

假设数组中有n个元素,在每一轮中,数组中的全部元素都将被遍历、比较、交换一遍,时间复杂度是O(n)。但由于分而治之,平均情况下只会进行O(logn)轮,因此快速排序算法的整体平均时间复杂度为O(nlogn)。

下面给出代码:

public class Quick {
    public static void main(String[] args) {
        QuickSort sort = new QuickSort();
        int [] arrays = new int[]{-1,0,3,5,7,9,6,3,4,5,12,8,6,5};
        sort.quickSort(arrays,0,arrays.length-1);
        System.out.println(Arrays.toString(arrays));
    }
}
class QuickSort{
    public void quickSort(int[]arrs,int startIndex,int endIndex){
        //跳出递归
        if(startIndex >= endIndex){
            return;
        }
        int pivot = sort(arrs,startIndex,endIndex);//取基准元素值
        quickSort(arrs,startIndex,pivot-1);//左区间递归
        quickSort(arrs,pivot+1,endIndex);//右区间递归
    }

    //双边循环法,返回pivot的位置
    public int sort(int[] arrs,int startIndex,int endIndex){
        //选第一个作为基准元素,当第一个作为基准元素时,如果恰好是最大值或最小值,会导致分治法失效,
        //因为这种情况下无法将数组分成两个子数组,算法时间复杂度会退化成O(n2)。这里也可以在区间内随机一个数,作为基准元素
        int pivot = arrs[startIndex];
        int left = startIndex;
        int right = endIndex;
        while (left!=right){
            while (left<right&&arrs[right]> pivot)right--;
            while (left<right&&arrs[left] <= pivot)left++;
            //交换左右两边的元素
            if(left<right){
                int l = arrs[left];
                arrs[left] = arrs[right];
                arrs[right] = l;
            }
        }
        if(left == right){
            arrs[startIndex] = arrs[left];
            arrs[left] = pivot;
        }
        return left;
    }

}

上面用的是双边循环法,在每个区间中利用首尾两个指针向中间逼近的方式,找到基准元素所在的位置。(说起来这种方式和三数之和中用到的双指针法蛮像的==)但这种方式虽然很直观,但代码量比较大,一个循环套两个循环有点令人头晕,因此还可以使用单边循环法,按照顺序遍历一遍,通过一个指针标识较小值区间和较大值区间的边界,达到分治的效果。

下面是单边循环法的实现:

//单边循环法,返回pivot的位置
public int sort1(int[] arrs,int startIndex,int endIndex){
    //选第一个作为基准元素,当第一个作为基准元素时,如果恰好是最大值或最小值,会导致分治法失效,
    //因为这种情况下无法将数组分成两个子数组,算法时间复杂度会退化成O(n2)
    int pivot = arrs[startIndex];
    int mark = startIndex;
    for (int i = startIndex;i<=endIndex;i++) {
        int val = arrs[i];
        if(val < pivot){
            mark++;//如果遍历值小于标准值,向右移动mark,较小值区间+1
            int p = arrs[mark];//交换该值与mark指向的值的位置
            arrs[mark] = val;
            arrs[i] = p;
        }
    }
    //交换mark指向的位置和pivot的位置
    arrs[startIndex] = arrs[mark];
    arrs[mark] = pivot;
    return mark;
}

看,只要一个大循环就完事了,简明扼要(