排序算法

[hankviv]

快速排序：分治思想，把大的排序 切成小的排序，一直切到两个数字比较，然后再合并数组

   function quickSorts($arr)
    {
        //递归终止条件
        if(count($arr) <= 1){
            return $arr;
        }
        //随机挑选一个元素，一般直接挑选第一个
        $key = $arr[0];
        $left = [];
        $right = [];
        //小于的放左边，大于的放右边
        for($i=1;$i<count($arr);$i++){
            if ($arr[$i] < $key){
                $left[] = $arr[$i];
            }else{
                $right[] = $arr[$i];
            }
        }
        //递归
        $left = quickSorts($left);
        $right = quickSorts($right);
        //把左边的 中间的 右边的合并起来
        return array_merge($left,[$key], $right);
    }

[hankviv]

选择排序：每次遍历 都选择到一个的最小的数，每次循环都拿到最小的数

func selectionSort(arr []int) []int {
    for i:=0; i<len(arr); i++  {
        min := i
        for j := i+1;j<len(arr);j++{
            if arr[i] > arr[j]{
                min = j
            }
        }
        arr[i],arr[min] = arr[min],arr[i]
    }
    return arr
}

[hankviv]

冒泡： 两两比较，每次遍历最大的在最后一位

func bubbleSort(nums []int) []int {
    for i:=0; i<len(nums) ; i++  {
        for j :=1; j<len(nums) - i -1; j++{
            if nums[j] > nums[j+1]{
                nums[j],nums[j+1] = nums[j+1],nums[j]
            }
        }
    }
    return nums
}

[hankviv]

稳定性：两个相同的的元素，排序后相对顺序不变。 稳定：冒泡、插入、归并和基数。 不稳定：选择、快速、希尔、堆。

比如选择排序的 时候 [5 9 5 2]第一次选择的时候 把第一个5和2交换了，但是稳定性要求排序完后第一个5要在第二个5前面，所以选择排序是不稳定的。