各大排序算法的时间空间复杂度

2018-04-04 13.51.45.jpeg

定义

快速排序是由冒泡排序进化而来。

• 在数据集之中，选择一个元素作为"基准"（pivot），一般选择第一个或者最后一个；
• 所有小于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素，都移到"基准"的右边。
• 对"基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止；

image.png

JAVA语言实现

private static void quickSort(int[] array, int left, int right) {
        int pivot,temp,i,j;
        if(left >= right) {
            return;
        }
        //p就是基准数,这里就是每个数组的第一个
        pivot = array[left];
        i = left;
        j = right;
        while(left < right) {
            //右边当发现小于pivot的值时停止循环
            while(array[right] >= pivot && left < right) {
                right--;
            }
            //这里一定是右边开始，上下这两个循环不能调换（下面有解析，可以先想想）
            //左边当发现大于pivot的值时停止循环
            while(array[left] <= pivot && left < right) {
                left++;
            }
            temp = array[right];
            array[right] = array[left];
            array[left] = temp;
        }
        array[i] = array[left];//pivot与left值互换
        array[left] = pivot;
        quickSort(array,i,left);  //对左边快排
        quickSort(array,left+1,j); //对右边快排

    }

  public static void main(String[] args) {
        int[] array = new int[]{4, 3,  2, 7, 8, 5, 1, 9, 6,1,2};
        quickSort(array, 0, array.length - 1);
        System.out.println("res = "+ Arrays.toString(array));

    }
}

时间复杂度

• 最好情况：乱序
• 最差情况：当序列本身就是正序或者逆序的时候，每次取的基准数是最大或者最小，这样划分的两个子集元素分别是n-1和0个元素，这种情况就相当于一个普通的冒泡排序其实
• 平均情况：乱序

附上冒泡的简单JAVA版本

    public  static int[] popSort(int [] nums) {
        for (int i =0 ;i < nums.length ;i++) {
            for (int j =i+1 ;j < nums.length ;j++) {
                if (nums[i] < nums[j]) {
                    int temp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = temp;
                }
            }
        }
        return nums;
    }

参考
https://pianshen.com/article/5011317794/