常见排序算法 - Java语言实现

选择排序

内层循环每次选择最小元素(用索引表示)，与数组中未排序部分的首元素进行交换。

public void selectSort(int[] nums) {
    int N = nums.length;
    for (int i = 0; i < N; i++) {
        int min = i; // 最小值的索引
        for (int j = i + 1; j < N; j++) {
            if (nums[j] < nums[min]) {
                min = j;
            }
        }
        exch(nums,i,min);
    }
}

public void exch(int[] nums,int a,int b){
    int temp=nums[a];
    nums[a]=nums[b];
    nums[b]=temp;
}

插入排序

内层循环每次从未排序部分中拿出一个元素，将其插入到已排序部分的合适位置。

public void insertSort(int[] nums){
    int N=nums.length;
    for (int i = 1; i < N; i++) {
        for (int j = i; j >0 ; j--) {
            if (nums[j]<nums[j-1]){
                exch(nums,j,j-1);
            }
        }
    }
}

快速排序

快速排序是选择一个基准值，将数组切分为小于等于它的左半部分和大于等于它的右半部分，以及基准值本身。然后递归调用排序方法，对左右子数组进行排序。
分为3个步骤：切分 - 排序左子数组 - 排序右子数组
关键是切分，每次切分完成后，都会排定基准值的最终位置

public void quickSort(int[] nums)
{
    sort(nums,0,nums.length-1);
}

private static void sort(int[] nums,int low,int high)
{
    if(low >= high)
    {
        return;
    }
    // 切分
    int j = partition(nums,low,high);
    // 排序左半部分
    sort(nums,low,j - 1);
    // 排序右半部分
    sort(nums,j + 1,high);
}

// 切分数组，并确定切分元素的位置
// 随意地取 a[lo] 作为切分元素，即那个将会被排定的元素;
// 然后我们从数组的左端开始向右扫描直到找到一个大于等于它的元素;
// 再从数组的右端开始向左扫描直到找到一个小于等于它的元素;
// 这两个元素显然是没有排定的，因此交换它们的位置
private static int partition(int[] nums,int low,int high)
{
    int pivot = nums[low]; // 切分元素
    int left = low, right = high+1; // 左右扫描指针
    while(true)
    {
        // 从左往右扫描
        while(nums[++left] < pivot)
        {
            if(left == high)
            {
                break;
            }
        }

        // 从右往左扫描
        while(nums[--right] > pivot)
        {
            if(right == low)
            {
                break;
            }
        }

        // 左右指针相遇，扫描结束
        if(left >= right)
        {
            break;
        }

        // 交换扫描到的2个元素
        exch(nums,left,right);
    }

    // 将切分元素放到正确的位置
    exch(nums,low,right);
    return right;
}

原文：https://www.cnblogs.com/lypzzzzz/p/14985584.html