Алгоритм быстрой сортировки на Java

Question

Я пытаюсь реализовать программу алгоритма QuickSort на Java, но получаю неправильный ответ.

public class QuickSort {

    public static void main(String[] args){
        int arr[]={12,34,22,64,34,33,23,64,33};
        int i=0;
        int j=arr.length;
        while(i<j){
            i=quickSort(arr,i,i+1,j-1);

        }   
        for(i=0;i<arr.length;i++)
            System.out.print(arr[i]+" ");
    }

    public static int quickSort(int arr[],int pivot,int i,int j){

        if(i>j) {           
            swap(arr,pivot,j);
            return i;
        }

        while(i<arr.length&&arr[i]<=arr[pivot]) {
            i++;
        }

        while(j>=1&&arr[j]>=arr[pivot]) {           
            j--;
        }   
        if(i<j)
            swap(arr,i,j);

        return quickSort(arr,pivot,i,j);

    }   
    public static void swap(int[] arr,int i,int j) {
        int temp;
        temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }

}

Приведенная выше программа выдала мне вывод:

Может ли кто-нибудь сказать мне, как я могу получить результат моего желания?

Answer 1

Проблема в том, что это не совсем так, как работает быстрая сортировка. Быстрая сортировка - это рекурсивный алгоритм, который должен вызываться только один раз извне. Идея состоит в том, что на каждой итерации вы разбиваете массив на две половины - левая половина содержит все элементы, меньшие, чем сводная, а правая половина содержит все элементы, большие или равные сводной. Затем вы быстро сортируете две половины и, наконец, ставите ось посередине.

Если сторона, которую вы сортируете, имеет длину менее 3 элементов, вы можете просто поменять местами два элемента или оставить их, и эта часть массива готова.

Но не похоже, что ваш код делает это вообще - вы вызываете Quicksort 6 раз со своего клиента, а в функции quicksort вы делаете не более одного обмена. Так что это не тот случай, когда кто-то сможет посмотреть на ваш код и отладить его, сказав, что нужно перенести своп или что-то в этом роде. Вам нужно пересмотреть свою логику.

Посмотрите на диаграмму Википедии для наглядного примера того, что должно происходить за одну итерацию:

http://en.wikipedia.org/wiki/File:Partition_example.svg

Answer 2

Существуют реализации быстрой сортировки с открытым исходным кодом в Apache Harmony и Apache Mahout, возможно, среди многих других. Вы можете прочитать их.

Answer 3

вот алгоритм быстрой сортировки

package drawFramePackage;
    import java.awt.geom.AffineTransform;
    import java.util.ArrayList;
    import java.util.ListIterator;
    import java.util.Random;
    public class QuicksortAlgorithm {
        ArrayList<AffineTransform> affs;
        ListIterator<AffineTransform> li;
        Integer count, count2;
        /**
         * @param args
         */
        public static void main(String[] args) {
            new QuicksortAlgorithm();
        }
        public QuicksortAlgorithm(){
            count = new Integer(0);
            count2 = new Integer(1);
            affs = new ArrayList<AffineTransform>();
            for (int i = 0; i <= 128; i++){
                affs.add(new AffineTransform(1, 0, 0, 1, new Random().nextInt(1024), 0));
            }
            affs = arrangeNumbers(affs);
            printNumbers();
        }
        public ArrayList<AffineTransform> arrangeNumbers(ArrayList<AffineTransform> list){
            while (list.size() > 1 && count != list.size() - 1){
                if (list.get(count2).getTranslateX() > list.get(count).getTranslateX()){
                    list.add(count, list.get(count2));
                    list.remove(count2 + 1);
                }
                if (count2 == list.size() - 1){
                    count++;
                    count2 = count + 1;
                }
                else{
                count2++;
                }
            }
            return list;
        }
        public void printNumbers(){
            li = affs.listIterator();
            while (li.hasNext()){
                System.out.println(li.next());
            }
        }
    }

также доступно с описанием на компьютерные знания Натана с описанием [код] [/код] ``

Answer 4

public static int partition(int[] a, int p, int r){

        int i=p,j=r,pivot=a[r];

        while(i<j){

            while(i<r && a[i] <= pivot){
                i++;
            }

            while(j>p && a[j]>pivot){ 
                j--;
            }

            if(i<j){
                swap(a, i, j);
            }           
        }   
        return j;
    }

    public static void quickSort(int[] a, int p, int r){
        if(p<r){
            int q=partition(a, p, r);

            if(p==q){
                quickSort(a, p+1, r);
            }else if(q==r){
                quickSort(a, p, r-1);
            }else {
                quickSort(a, p, q);
                quickSort(a, q+1, r);
            }

        }
    }

    public static void swap(int[] a, int p1, int p2){
        int temp=a[p1];
        a[p1]=a[p2];
        a[p2]=temp;
    }

Answer 5

Ваш цикл не работает должным образом. Обратитесь к коду, который решит вашу проблему о Быстрая сортировка

static void quickSort (int[] numbers, int low, int high)
{
    int i=low;
    int j=high;
    int temp;
    int middle=numbers[(low+high)/2];

    while (i<j) {

        while (numbers[i]<middle) {
            i++;
        }

        while (numbers[j]>middle) {
            j--;
        }

        if (i<=j) {
            temp=numbers[i];
            numbers[i]=numbers[j];
            numbers[j]=temp;
            i++;
            j--;
        }
    }

    if (low<j) {
        quickSort(numbers, low, j);
    }

    if (i<high) {
        quickSort(numbers, i, high);
    }
}

См. Быстрая сортировка.

Answer 6

Подробный рабочий код для алгоритма быстрой сортировки, реализованного в Java, можно найти здесь,

http://tech.bragboy.com/2010/01/quick-sort-in-java.html