在快速排序的应用程序，这些线路的交换code的目的是什么？ [英] What is the purpose of these lines of swap code in quicksort application?

问题描述

我想了解的实施或快速排序的应用程序查找第k个最小元素 这里是code，我想了解

 公众诠释快速排序（INT A []，诠释开始，诠释年底，INT K）{
    如果（开始＆LT;结束）{
        INT支点=分区（A，开始，结束）;
        如果（枢轴== K -1）{
            返回支点;
        }否则如果（支点＆GT; k  -  1）{
            返回快速排序（A，启动，支点，K）;
        } 其他 {
            返回快速排序（一个，枢轴+ 1，结束，k）的;
        }
    }否则，如果（开始==结束）{
        复位K == 1日开始：-1;？
    } 其他 {
        返回-1;
    }
}
公众诠释分区（INT A []，诠释开始，诠释完）{
    INT支点=启动;
    INT I =支点+ 1;
    INT J =结束;
    而（一个[1]  - ;一个[枢轴]安培;＆安培; I＆所述端）{
        我++;
    }
    而（一个[j]的＆gt;一种[枢轴]安培;＆安培; J＆GT; = 0）{
        的J  - ;
    }
    如果（ⅰ＆所述; j）条{
        掉期（一，开始，结束）;
    }
    交换（A，J枢轴）;
    返回支点;
}
私人无效掉期（INT A []，INT swap1，诠释swap2）{
    INT TEMP = A [swap1]
    一个[swap1] = A [swap2]
    一个[swap2] =气温;
}
 

予理解为努力寻找k个最小的元素，要使用快速排序，因为元素以枢轴的左侧将小于枢轴和元素枢轴将大于右侧。这样一来，如果你想找到4最小的元素，和枢轴是指数3，你可以返回它，因为你知道它是第四最小的，因为有3个因素比它更小。

我无法理解的划分方法两个互换。

目前第一结束while循环中，索引i将在一个位置处小于枢轴所有元素将是i的左侧。索引j将是在一个位置上比枢轴更大所有元素将到j的右侧。

什么内部分区此交换code的目的是什么？ 谁能给的code，为什么这是必要的一个例子吗？如何将这些不断满足？

 如果（I＆LT; j）条{
        掉期（A，I，J）;
}
 

，也为这个互换额度（也在里面分区），为什么笔者交换枢纽和j，而不是转动而我呢？是乱？

 掉期（A，J支点）;
 

解决方案

您可以使用分区算法present为：的快速排序划分算法

您使用的是返回不正确的支点算法

I am trying to understand an implementation or an application of quicksort to find the kth smallest element Here is the code that I am trying to understand

public int quicksort(int a[], int start, int end, int k) {
    if(start < end) {
        int pivot = partition(a, start, end);
        if(pivot == k -1) {
            return pivot;
        } else if(pivot > k - 1){
            return quicksort(a, start, pivot, k);
        } else {
            return quicksort(a, pivot + 1, end, k);
        }
    } else if(start == end) {
        return k==1?start:-1;
    } else {
        return -1;
    }
}
public int partition(int a[], int start, int end) {
    int pivot = start;
    int i = pivot + 1;
    int j = end;
    while(a[i] < a[pivot] && i < end) {
        i ++;
    } 
    while(a[j] > a[pivot] && j >= 0) {
        j --;
    } 
    if(i < j) {
        swap(a, start, end);
    }
    swap(a,j, pivot);
    return pivot;
}
private void swap(int a[], int swap1, int swap2) {
    int temp = a[swap1];
    a[swap1] = a[swap2];
    a[swap2] = temp;
}

I understand for trying to find the kth smallest element, you want to use quicksort because elements to the left of pivot will be less than the pivot and elements to the right of the pivot will be greater than. So that way if you're trying to find the 4th smallest element, and the pivot is at index 3, you can just return it because you know it is the 4th smallest since there are 3 elements smaller than it.

I am having trouble understanding the two swaps in the partition method.

At the conclusion of the first while loop, index i will be at a position at which all elements less than the pivot will be to the left of i. Index j will be at a position at which all elements greater than the pivot will be to the right of j.

What is the purpose of this swap code inside partition? Can anyone give an example of why this of code is necessary? How will these ever meet?

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

And also for this swap line(also inside partition), why did the author swap pivot and j, and not pivot and i? Is it arbitrary?

        swap(a,j, pivot);

解决方案

You can use the partition algorithm present at : Quick sort partition algorithm

The algorithm you are using returns incorrect pivot

这篇关于在快速排序的应用程序，这些线路的交换code的目的是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！