快速排序实现尝试

Question

在 youtube 上观看了这个视频后，我试图编写一个快速排序实现。 https://www.youtube.com/watch?v=MZaf_9IZCrc&t=215s 但它不起作用。有人可以告诉我我做错了什么吗？谢谢费尔达

 public class Trial{

     public static void main(String []args){
        int arr[] = {7, 3, 4, 2, 6, 1, 5};
        quickSort(arr, 0, 6);
     }


     public static void quickSort(int[] arrInput, int start, int end){

         int arr[] = new int[end-start+1];
         for(int i=start, j=0; i<end; i++, j++){
             arr[j]=arrInput[i];
         }
         int size = arr.length;
         int pivotValue = arr[size-1];

         for (int i=-1; i<arr.length; i++){
           for(int j=0; j<arr.length; j++){
            if(arr[j]< pivotValue){
                int temp = arr[j];
                i++;
                arr[j] = arr[i];
                arr[i] = temp;
            }
            for(int p = i; p< size-2; p++ ){
                arr[p+1] = arr[p];
            }
            arr[i] = pivotValue;
            quickSort(arr, 0, i);
            quickSort(arr, i+1, size-1);
           }
         }

      }
}

Answer 1

快速排序就是这样的：

public static void quicksort(int[] array, int begin, int end) {
    if (array == null || array.length() == 0) {
        return;
    }
    int pivot = partition(array);
    quicksort(array, 0, pivot);
    quicksort(array, pivot + 1, array.length);
}

public static void quicksort(int[] array) {
    quicksort(array, 0, array.length());
}

之后就可以用你的视频实现分区方法了

Answer 2

你在这里提到的视频，讲述了分区 mechanism.So 值小于 pivot 的元素出现在 pivot 之前，元素值大于 pivot 出现在 pivot 之后（相等可以任意）。有两个部分如果是快速排序算法， partition 和 quicksort 。 Quicksort 是in place sort，这里不需要新建数组。而你选择了最后一个元素作为枢轴元素，你可以按照下面给出的伪代码来实现快速排序：

quicksort(A, lo, hi) is
if lo < hi then
    p := partition(A, lo, hi)
    quicksort(A, lo, p – 1)
    quicksort(A, p + 1, hi)



partition(A, lo, hi) is
    pivot := A[hi]
    i := lo     // place for swapping
    for j := lo to hi – 1 do
        if A[j] ≤ pivot then
            swap A[i] with A[j]           
            i := i + 1
swap A[i] with A[hi]
return i

快速排序实现尝试

Quick Sort Implementation Attempt

java

quicksort