0

我有以下数组：

int[] arr = { 19, 4, 2, 3, 9, 2, 10, 2, 7, 12, 5, 16, 8, 3, 11, 14, 0, 5 };

现在我使用快速排序的分区来对具有枢轴元素 7 的数组进行分区：

    public static void partition(int[] arr, int low, int high) {
    int pivot = arr[low + (high - low) / 2];
    int i = low;
    int j = high;
    while (i <= j) {
        // If the current value from the left list is smaller then the pivot
        // element then get the next element from the left list
        while (arr[i] < pivot) {
            i++;
        }
        // If the current value from the right list is larger then the pivot
        // element then get the next element from the right list
        while (arr[j] > pivot) {
            j--;
        }

        // If we have found a values in the left list which is larger then
        // the pivot element and if we have found a value in the right list
        // which is smaller then the pivot element then we exchange the
        // values.
        // As we are done we can increase i and j
        if (i <= j) {
            swap(arr, i, j);
            i++;
            j--;
        }
    }
}

我对结果感到困惑：

5 4 2 3 0 2 3 2 5 12 7 16 8 10 11 14 9 19

我认为每个元素 <= pivot (7) 必须在左侧，并且每个元素 > 比枢轴元素必须在右侧。但是为什么 12 剩下 7 呢？

4

3 回答 3

1

此实现无法保证您的期望。它所做的只是以下内容（前提是您更改为arr[i] <= pivot，正如 Achintya Jha 建议的那样，否则它甚至无法保证）：

对于每对a, b带有的值a <= pivot < b，保证a最终会被留下b。但是，您不能保证最终数组中的确切位置pivot（仅保证它位于所有较大值的左侧）。

于 2013-05-04T13:23:39.863 回答
0

为快速排序方法创建一个类

package com.Ramesh;

public class QuickSort {

public void sort(int[] a,int left,int right){
    if(left<right)
    {
        int partition=getPartition(a, left, right);
        sort(a,left,partition-1);
        sort(a,partition+1,right);
    }
}
public int getPartition(int[] a,int l,int r)
{
    int pivot=a[l];
    int left=l;
    int right=r;
    while(left<right)
    {
        while(a[left]<pivot){
            left++;
        }

        while(a[right]>pivot){
            right--;
        }

        if(left<right){
            int temp=a[left];
            a[left]=a[right];
            a[right]=temp;
        }

    }
    return right;
}

}

2.创建另一个类来调用排序方法 

import java.util.Scanner;
public class Execute {

    private int[] a;
    private int len;

    public int[] getA() {
        return a;
    }

    public void setA(int[] a) {
        this.a = a;
    }

    public int getLen() {
        return len;
    }

    public void setLen(int len) {
        this.len = len;
    }

    public static void main(String[] args) {
        Execute ex=new Execute();
        ex.takeInput();
        QuickSort q=new QuickSort();
        q.sort(ex.getA(),0,ex.getLen()-1);
        System.out.println("Printing the the Sorted Object");
        System.out.println(ex);
        }

    public void takeInput()
    {
        Scanner s1=new Scanner(System.in);
        System.out.println("Please enter the no of element to be sorted");
        len=s1.nextInt();
        a=new int[len];
        System.out.println("Pls enter the elements");
        for(int i=0;i<len;i++){
            a[i]=s1.nextInt();
        }

    }

    @Override
    public String toString(){
        StringBuffer s=new StringBuffer("");
        for(int i=0;i<this.len;i++){
            s.append(this.a[i]+"\n");
        }
        return s.toString();

    }

}
于 2014-09-15T06:10:37.340 回答
0

C++ 中的partition函数如下所示：

  while (first!=last) {
    while (pred(*first)) {
      ++first;
      if (first==last) return first;
    }
    do {
      --last;
      if (first==last) return first;
    } while (!pred(*last));
    swap (*first,*last);
    ++first;
  }
  return first;

First并且last是指向数组中元素的迭代器，类似于你的i和j变量。pred是谓词的缩写，i <= 7例如。本质上，此函数返回中点，因此在 C++ 代码中，您将通过向上迭代获得中点左侧的所有元素，并通过从中点迭代到末尾获得所有右侧的元素。为了减少混淆：

i 应该是第一个元素， j 应该是最后一个元素。

// 先获取中点

...

// Note. <= is the opposite of >
// Which logically is the same as
// pred is the opposite of !pred
  while (i != j) {
    while (i <= midpoint) {
      ++i;
      if (i == j) return i;
    }
    do {
      --j;
      if (i == j) return i;
    } while (i > midpoint);
    swap (i, j);
    ++i;
  }
  return i;

...

for (int i = 0; i < get_midpoint(...); i++)
for (int i = get_midpoint; i < end_of_array; i++)
于 2013-05-04T13:19:13.687 回答