java 快速排序算法 到底是錯在哪了

Question

import java.util.Arrays;
public class TestPaiXu {
public static void main(String[] args) {
int[] a = {1,5,4,3,2,1,1,8,9,49,12,46};
new TestPaiXu().Quick_Sort(a,0,a.length-1);
System.out.println(Arrays.toString(a));
}
void Quick_Sort(int A[],int low,int high)  //low和high是数组的下标
{
    if(low<high)
    {
        int temp,t=A[low];
        int l=low,h=high;
        while(l<h)
        {
            while(l < h && A[l]<t) l++;
            while(l < h && A[h]>=t) h--;
            if(h>l)
            {
                temp=A[l];
                A[l]=A[h];
                A[h]=temp;
            }
        }
     /*temp = t;
     t = A[l];
     A[l] = temp;
     System.out.println(temp);*/
     
        Quick_Sort(A,low,l-1);
        Quick_Sort(A,l+1,high);
        /*int m = A[low];
        A[low] = A[l];
        A[l] = m;*/
    }
}
}

Answer 1

直接Arrays.sort(a);
不就能排序了嘛……
何苦自己写一个

Answer 2

楼主也不编辑下
看的头疼啊
下边是我写的一个public static void quickSort(int[] arr) {
innerQuickSort(arr, 0, arr.length - 1);
} private static void innerQuickSort(int[] arr, int head, int end) {
if (head >= end) {
return;
}
int index = head;
for (int i = head; i < end; i++) {
if (arr[i] <= arr[end] && index != i) {
arr[index] ^= arr[i];
arr[i] ^= arr[index];
arr[index] ^= arr[i];
index++;
}
}
if (index != end) {
arr[index] ^= arr[end];
arr[end] ^= arr[index];
arr[index] ^= arr[end];
}
innerQuickSort(arr, head, index - 1);
innerQuickSort(arr, index + 1, end);
}

Answer 3

是吖 虽说是java程序员 但是精于算法还是很好的

Answer 4

首先来看下你运行程序的结果吧。first[8, 8, 71, 2, 3]
swap x[m]:8 l:0 h:4 :[3, 8, 71, 2, 8] 
swap x[m]:8 l:1 h:3 :[3, 2, 71, 8, 8] 
swap x[m]:8 l:2 h:2 :[3, 2, 71, 8, 8] 
swap x[m]:3 l:0 h:1 :[2, 3, 71, 8, 8] 
swap x[m]:3 l:1 h:1 :[2, 3, 71, 8, 8] 
swap x[m]:8 l:3 h:3 :[2, 3, 71, 8, 8] 
finally:[2, 3, 71, 8, 8]
那么为什么会出错呢？原因是在这里的
当你递归到71,8,8的时候，此时l=3,h=3,不进入循环，即为最后结果。
所以可以将算法改进一下即可public static int Quick_Sort(int A[],int low,int high) //low和high是数组的下标
{
int temp,l=0,h,t;
if(low<high)
{
 t=A[low];
 l=low;
 h=high;
while(l<h)
{
while(l < h && A[l]<t) ++l;
if(h>l)                 //先将大的交换过来，是否比A【low】大不管
{
temp=A[l];
A[l]=A[h];
A[h]=temp;
}
while(l < h && A[h]>=t) --h;
if(h>l)
{
temp=A[l];
A[l]=A[h];
A[h]=temp;
}

System.out.printf("swap x[m]:%d l:%d h:%d :%s \n",t,l,h,Arrays.toString(A));
//System.out.printf("swap x[m]:%d %d %d:%s\n", x[m],i, j, Arrays.toString(x));
}
/*temp = t;
t = A[l];
A[l] = temp;
System.out.println(temp);*/ /*int m = A[low];
A[low] = A[l];
A[l] = m;*/

}
return l;
}

Answer 5

public static int Quick_Sort(int A[],int low,int high) //low和high是数组的下标
        {
        int temp,l=0,h,t;
        if(low<high)
        {
         t=A[low];
         l=low;
         h=high;
        while(l<h)
        {
        while(l < h && A[l]<t) ++l;
        if(h>l)                 //先将大的交换过来，是否比A【low】大不管
        {
        temp=A[l];
        A[l]=A[h];
        A[h]=temp;
        }
        while(l < h && A[h]>=t) --h;
        if(h>l)
        {
        temp=A[l];
        A[l]=A[h];
        A[h]=temp;
        }
        
        System.out.printf("swap x[m]:%d l:%d h:%d :%s \n",t,l,h,Arrays.toString(A));
        //System.out.printf("swap x[m]:%d %d %d:%s\n", x[m],i, j, Arrays.toString(x));
        }
        /*temp = t;
        t = A[l];
        A[l] = temp;
        System.out.println(temp);*/        /*int m = A[low];
        A[low] = A[l];
        A[l] = m;*/
        
        }
        return l;
        }

Answer 6

直接用Arrays.sort(a);排序方法，方便简洁；

Answer 7

public static void qsort_no_recursion(int[] src) {
int[][] arr = new int[src.length][2];
int count = 0, index = 0;
arr[0][0] = 0;
arr[0][1] = src.length - 1;
while (index <= count) {
int left = arr[index][0];
int right = arr[index][1];
int[] dir = { 0, 1 };
int i = left, j = right;
while (i < j) {
if (src[i] > src[j]) {
swap(src, i, j);
dir[0] = 1 - dir[0];
dir[1] = 1 - dir[1];
}
i += dir[0];
j -= dir[1];
}
if (j - left > 1) {
count++;
arr[count][0] = left;
arr[count][1] = j - 1;
}
if (right - i > 1) {
count++;
arr[count][0] = i + 1;
arr[count][1] = right;
}
index++;
}
}private static void swap(int[] src, int i, int j) {
if (i == j || i < 0 || i >= src.length || j < 0 || j >= src.length)
return;
src[i] ^= src[j];
src[j] ^= src[i];
src[i] ^= src[j];
}
无递归快排，不过需要额外的大小为n*2的空间public static void qsort(int[] src) {
qsort(src, 0, src.length - 1);
}private static void qsort(int[] src, int left, int right) {
if (left >= right || left < 0 || right >= src.length)
return; int[] dir = { 0, 1 };
int i = left, j = right;
while (i < j) {
if (src[i] > src[j]) {
swap(src, i, j);
dir[0] = 1 - dir[0];
dir[1] = 1 - dir[1];
}
i += dir[0];
j -= dir[1];
} if (j - left > 1) {
qsort(src, left, j - 1);
}
if (right - i > 1) {
qsort(src, i + 1, right);
}
}private static void swap(int[] src, int i, int j) {
if (i == j || i < 0 || i >= src.length || j < 0 || j >= src.length)
return;
src[i] ^= src[j];
src[j] ^= src[i];
src[i] ^= src[j];
}
一般的递归快排