Java & Js & Python 快速排序（2020年8月31日）

学习背景

大二上学期刚开学，学习了一点算法。参考着《数据解构》上C语言版的快速排序算法，经过理解记忆和练习，默写java、js、python版的快速排序。

源代码

Java

import java.util.Arrays;
public class test {
    public static void main(String[] args){
        int[] arr = {1, 3, 4, 2, 1, 3, 4, 2, 1, 3, 1, 2};
        quickSortArray(arr);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 对数组进行快速排序
     *
     */
    public static void quickSortArray(int[] array){
        //调用递归函数
        quickSort(array, 0, array.length - 1);
    }
    
    public static void quickSort(int[] array, int low, int high){
        if(low < high){
            int sign = parting(array, low, high);
            quickSort(array, low, sign - 1);
            quickSort(array, sign + 1, high);
        }
    }

    private static int parting(int[] array, int low, int high){
        int swapNum = low;
        for(int i = low; i < high; i++){
            System.out.println(i);
            if(array[i] < array[high]){
                swap(array, i, swapNum);
                swapNum++;
            }
        }
        swap(array, swapNum, high);
        return swapNum;
    }

    // 交换两个变量的值
    private static void swap(int[] array, int a, int b){
        int c = array[a];
        array[a] = array[b];
        array[b] = c;
    }
}

JavaScript

//交换数组中的两个变量
function swap(array, a, b){
    var c;
    c = array[a];
    array[a] = array[b];
    array[b] = c;
}
//快速排序
function quicklySort(array, low, high){
    if(low < high){
        var sign = partly(array, low, high);
        quicklySort(array, low, sign - 1);
        quicklySort(array, sign + 1, high);
    }
}

//快速排序中的分割函数
function partly(array, low, high){
    var i = low;
    for(var j = low; j < high; j ++){
        if (array[j] < array[high]){
            //array[i], array[j] = array[j], array[i];
            swap(array, i, j);
            i++;
        }
    }
    //array[i], array[high] = array[high], array[i];
    swap(array, i, high);
    return i;
}
//打印数组
function printArray(array){
    for(var i = 0; i < array.length; i++){
        document.write("<p>");
        document.write(array[i]);
        document.write("</p>");
    }
}

var a = new Array();
//在数组里添加很多随机数
for(var i = 0; i< 100; i++){
    a.push(Math.random());
}
document.write("<h1>");
document.write("排序前的数组");
document.write("</h1>");

printArray(a);

document.write("<h1>");
document.write("排序后的数组");
document.write("</h1>");

quicklySort(a, 0, a.length - 1);
printArray(a);

Python

def partition(array, low, high):
    """
    快速排序中用到的分割函数：
    重新排序数列，所有比基准值小的元素摆放在基准前面，
    所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。
    在这个分割结束之后，对基准值的排序就已经完成;
    @:param array 传入的数组，一小段
    @:param low 最小索引
    @:param high 最大索引
    @:return 一步分割后的基准值下标
    """
    i = low  # 最小元素索引
    # j 遍历 [low, high)，high 是基准值的下标，所以不包含 high
    for j in range(low, high):
        # 当元素小于或者等于基准值 array[high]
        if array[j] < array[high]:
            # 交换下标 i 和 j 的位置
            if i != j:
                array[i], array[j] = array[j], array[i]
            i += 1
    # 交换位置
    array[i], array[high] = array[high], array[i]
    return i


def quick_sort(array, low, high):
    """
    快速排序
    该函数直接修改了数组的状态
    :param array: 排序数组
    :param low: 起始索引
    :param high: 结束索引
    """
    if low <= high:
        pi = partition(array, low, high)
        quick_sort(array, low, pi - 1)  # 对前半部分排序
        quick_sort(array, pi + 1, high)  # 对后半部分排序


if __name__ == '__main__':
    arrayList = []
    for num in range(100000):
        arrayList.append(uniform(0, 100))

    t1 = time()
    quick_sort(arrayList, 0, len(arrayList) - 1)
    t2 = time()
    print(t2 - t1)
    pass