求使用java实现的快排算法

2025-03-02 04:09:26

推荐回答（2个）

回答1：

① 代码：

public class quicksortdemo {
    
    private int array[];
    private int length;

    public void sort(int[] inputArr) {
        
        if (inputArr == null || inputArr.length == 0) {
            return;
        }
        this.array = inputArr;
        length = inputArr.length;
        quickSort(0, length - 1);
    }

    private void quickSort(int lowerIndex, int higherIndex) {
        
        int i = lowerIndex;
        int j = higherIndex;
        // calculate pivot number
        int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2];
        // Divide into two arrays
        while (i <= j) {
            while (array[i] < pivot) {
                i++;
            }
            while (array[j] > pivot) {
                j--;
            }
            if (i <= j) {
                swap(i, j);                
                i++;
                j--;
            }
        }
        // call quickSort() method recursively
        if (lowerIndex < j)
            quickSort(lowerIndex, j);
        if (i < higherIndex)
            quickSort(i, higherIndex);
    }

    private void swap(int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
    
    public static void main(String a[]){
        
        quicksortdemo sorter = new quicksortdemo();
        int[] input = {24,2,45,20,56,75,2,56,99,53,12};
        sorter.sort(input);
        for(int i:input){
            System.out.print(i);
            System.out.print(" ");
        }
    }
}

② 运行：

c:\>java quicksortdemo
2 2 12 20 24 45 53 56 56 75 99

回答2：

package com.quicksort;
import java.util.Arrays;
public class QuickSort {
public static void main(String[] args) {
int[] a = {1, 2, 4, 5, 7, 4, 5 ,3 ,9 ,0};
System.out.println(Arrays.toString(a));
quickSort(a);
System.out.println(Arrays.toString(a));
}
public static void quickSort(int[] a) {
if(a.length>0) {
quickSort(a, 0 , a.length-1);
}
}
private static void quickSort(int[] a, int low, int high) {
//1,找到递归算法的出口
if( low > high) {
return;
}
//2, 存
int i = low;
int j = high;
//3,key
int key = a[ low ];
//4，完成一趟排序
while( i< j) {
//4.1 ，从右往左找到第一个小于key的数
while(i key){
j--;
}
// 4.2 从左往右找到第一个大于key的数
while( i
i++;
}
//4.3 交换
if(i
int p = a[i];
a[i] = a[j];
a[j] = p;
}
}
// 4.4，调整key的位置
int p = a[i];
a[i] = a[low];
a[low] = p;
//5, 对key左边的数快排
quickSort(a, low, i-1 );
//6, 对key右边的数快排
quickSort(a, i+1, high);
}
}