java - 递归随机枢轴排序的问题

Question

我在编写一个递归函数来对 java 中的数组进行递归排序时遇到了一些问题。现在看起来好像我有一个无限循环，而且我似乎不知道在哪里。

主函数“rec_piv”从索引1搜索到枢轴点并对前半部分进行排序，然后从枢轴点切换到数组的长度并对后半部分进行排序。所有的比较都由一个 int 记录。 [数组大小从2到2014随机]

提前非常感谢!

public class Recursive_pivot {

    private Random random_size = new Random();
    private int size = random_size.nextInt(1024) + 2;
    public int[] a = new int[size];
    private Random elements = new Random();
    /* variable for rec_piv   */
    public int temp=0;
    public int temp2=0;
    private Random rand_pivot = new Random();
    private int pivot = rand_pivot.nextInt(size) + 2;
    private int first_half =a[0+1];
    private int second_half=a[pivot+1];
    private int first_index=0; //first half of the array
    private int second_index=pivot; //second half of the array
    //The pivot is randomly chosen.
    public int comparisons =0; //count the number of comparisons.

    public void fill(){
        for (int q=0; q<a.length; q++) {
            /* filling the array */
            a[q] = elements.nextInt(100 ) + 1;
        }
    }


    public void rec_piv(int first_index, int second_index) {
        if(first_index < pivot) {
            if(first_half > a[first_index]) {
                comparisons++;

                temp = a[first_index];
                a[first_index] = a[first_half];
                a[first_half] = temp;
            }

            rec_piv(first_index+1, second_index);
        }

        if(second_index < a.length) {
            if(second_half > a[second_index]) {
                comparisons++;

                temp2 = a[second_index];
                a[second_index] = a[second_half];
                a[second_half] = temp2;
            }
            rec_piv(first_index, second_index+1);
        }

    } //end of rec_piv

}//end of class.

Answer 1

您正在尝试进行 QSort，这是它的一个简单版本。

public void quickSort(int array[], int start, int end)
{
    int i = start;                          // index of left-to-right scan
    int k = end;                            // index of right-to-left scan

    if (end - start >= 1)                   // check that there are at least two elements to sort
    {
            int pivot = array[start];       
            while (k > i)                   
            {
                while (array[i] <= pivot && i <= end && k > i)                            
                    i++;                                    
                while (array[k] > pivot && k >= start && k >= i) 
                    k--;                                        
                if (k > i)                                       
                    swap(array, i, k);                      
            }
            swap(array, start, k);                                                          
            quickSort(array, start, k - 1); // quicksort the left partition
            quickSort(array, k + 1, end);   // quicksort the right partition
    }
    else    // if there is only one element in the partition, do not do any sorting
    {
            return;                     // the array is sorted, so exit
    }
 }

 public void swap(int array[], int index1, int index2) 
 // pre: array is full and index1, index2 < array.length
// post: the values at indices 1 and 2 have been swapped
{
int temp = array[index1];           // store the first value in a temp
array[index1] = array[index2];      // copy the value of the second into the first
array[index2] = temp;               // copy the value of the temp into the second
}

来自此网站。 http://www.mycstutorials.com/articles/sorting/quicksort