数据结构-快速排序 java实现-蒲公英云

数据结构-快速排序 java实现

快速排序又可以分为冒泡排序、快速排序

1、冒泡排序:时间复杂度O(n*n)。算法思想：每一次排序都会将最大或者最小的数沉到最下面。

<span style="font-size:14px;">public static void bubbleSort(int [] num){
       int length=num.length;
       for(int i=0;i<length;i++){
           for(int j=0;j<length-i-1;j++){
               int temp;
               if(num[j]>num[j+1])
               {
                   temp=num[j];
                   num[j]=num[j+1];
                   num[j+1]=temp;               
               }
           }
       }
    }</span>

2、快速排序：使用递归的思想，先任意在数组中选择一个基准将数组分成两个部分，然后再分别对这两个部分进行快速排序，时间复杂度为：O（nlog2n）

<span style="font-size:14px;">/**
     * description : 快速排序
     */
    public static void quicksort(int n[], int left, int right) {
        int dp;
        if (left < right) {
            dp = partition(n, left, right);
            quicksort(n, left, dp - 1);
            quicksort(n, dp + 1, right);
        }
    }
    public static int partition(int n[], int left, int right) {
        int pivot = n[left];
        while (left < right) {
            while (left < right && n[right] >= pivot)
                right--;
            if (left < right)
                n[left++] = n[right];
            while (left < right && n[left] <= pivot)
                left++;
            if (left < right)
                n[right--] = n[left];
        }
        n[left] = pivot;
        return left;
    }</span>