常见排序算法

常见排序算法分类:

(1) 插入排序:直接插入排序、二分法插入排序、希尔排序

(2) 选择排序:直接选择排序、堆排序

(3) 交换排序:冒泡排序、快速排序

(4) 归并排序

(5) 基数排序

一、插入排序

1、直接插入排序

每步从待排序列首位取出一个元素,然后从已排序列末端出发,依次比较大小和移位找到合适的位置插入,直到待排序列全部插入为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function directInsertSort(array &$numArr) {
    $len = count($numArr);
    if ($len <= 1) {
        return;
    }
    for ($i = 1; $i < $len; $i++) {
        $thisNum = $numArr[$i];
        $j = $i - 1;
        while ($j >= 0) {
            if ($numArr[$j] > $thisNum) {
                $numArr[$j + 1] = $numArr[$j];
            } else {
                break;
            }
            $j--;
        }
        $numArr[$j + 1] = $thisNum;
    }
}

2、二分插入排序

每步从待排序列首位取出一个元素,然后对已排序列进行二分查询,找到合适的位置插入,直到待排序列全部插入为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function binaryInsertSort(array &$numArr) {
    $len = count($numArr);
    if ($len <= 1) {
        return;
    }
    for ($i = 1; $i < $len; $i++) {
        $thisNum = $numArr[$i];
        $low = 0;
        $high = $i - 1;
        while ($low <= $high) {
            $mid = $low + (($high - $low) >> 1); // 防止溢出 & 移位效率更高
            if ($numArr[$mid] > $thisNum) {
                $high = $mid - 1;
            } else {
                $low = $mid + 1;
            }
        }
        for ($j = $i - 1; $j >= $low; $j--) {
            $numArr[$j + 1] = $numArr[$j];
        }
        $numArr[$low] = $thisNum;
    }
}

3、希尔排序

有一个递减的增量序列,遍历此序列把待排数组按照增量进行分组,然后对每个分组进行直接插入排序,直到增量减至1时,整个数组即为有序。

关键思想:因为直接插入排序插入基本有序的序列时效率更高。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function shellSort(array &$numArr) {
    $len = count($numArr);
    if ($len <= 1) {
        return;
    }
    for ($gap = $len >> 1; $gap > 0; $gap >>= 1) { // 增量序列为折半减少
        // 以下进行直接插入排序
        for ($i = $gap; $i < $len; $i += $gap) {
            $thisNum = $numArr[$i];
            $j = $i - $gap;
            while ($j >= 0) {
                if ($numArr[$j] > $thisNum) {
                    $numArr[$j + $gap] = $numArr[$j];
                } else {
                    break;
                }
                $j -= $gap;
            }
            $numArr[$j + $gap] = $thisNum;
        }
    }
}

二、选择排序

1、直接选择排序

从待排序列中选出最小(或最大)的数与第一个位置的数交换,然后再在剩下的数中查找最小(或最大)的数与第二个位置的数交换,如此循环到待排序列为空。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function directSelectSort(array &$numArr) {
    $len = count($numArr);
    if ($len <= 1) {
        return;
    }
    for ($i = 0; $i < $len - 1; $i++) {
        $minIndex = $i;
        for ($j = $i + 1; $j < $len; $j++) {
            if ($numArr[$j] < $numArr[$minIndex]) {
                $minIndex = $j;
            }
        }
        $minVal = $numArr[$minIndex];
        $numArr[$minIndex] = $numArr[$i];
        $numArr[$i] = $minVal;
    }
}

2、堆排序

把初始序列看成一个顺序存储的二叉树,调整它的顺序使之成为一个堆,这时根节点最大;然后将根节点与最后一个节点进行交换,再对前n-1个数重新建堆,以此类推;直到建堆序列为空。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
function hellSort(array &$numArr) {
    $len = count($numArr);
    if ($len <= 1) {
        return;
    }
    // 循环建堆
    for ($i = 0; $i < $len - 1; $i++) {
        // 建堆
        $lastIndex = $len - 1 - $i;
        for ($j = ($lastIndex - 1) >> 1; $j >= 0; $j--) { // 从最后一个节点的父节点出发
            $thisIndex = $j;
            // 整理对比此父节点和左右子节点使得父节点最大
            while (2 * $thisIndex + 1 <= $lastIndex) { // 左子节点存在
                $maxSubIndex = 2 * $thisIndex + 1;
                if ($maxSubIndex < $lastIndex && 
                    $numArr[$maxSubIndex + 1] > $numArr[$maxSubIndex]
                ) { // 右子节点存在且较大
                    $maxSubIndex++;
                }
                if ($numArr[$maxSubIndex] > $numArr[$thisIndex]) { // 较大的子节点比父节点大
                    $temp = $numArr[$thisIndex];
                    $numArr[$thisIndex] = $numArr[$maxSubIndex];
                    $numArr[$maxSubIndex] = $temp;
                    $thisIndex = $maxSubIndex; // 子节点变化需重新整理该节点的下一层子节点
                } else {
                    break;
                }
            }
        }
        // 堆顶元素置后加入已排序列
        $temp = $numArr[0];
        $numArr[0] = $numArr[$lastIndex];
        $numArr[$lastIndex] = $temp;
    }
}

三、交换排序

1、冒泡排序

对相邻的两个数两两作比较,较大者往后冒,这样每趟遍历最后的数为最大,把它剔除出去;再对前面的n-1个数进行两两对比交换,直到没有相邻的数进行比较交换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function bubbleSort(array &$numArr) {
    $len = count($numArr);
    if ($len <= 1) {
        return;
    }
    for ($i = $len - 1; $i > 0; $i--) {
        for ($j = 0; $j < $i; $j++) {
            if ($numArr[$j] > $numArr[$j + 1]) {
                $temp = $numArr[$j];
                $numArr[$j] = $numArr[$j + 1];
                $numArr[$j + 1] = $temp;
            }
        }
    }
}

2、快速排序

选取一个基准元素(通常选择第一个元素),通过头尾交替对比的方法,使待排序列分成两部分,一部分比基准元素小,另一部分大于等于基准元素,这样,基准元素刚好排在了排好序后的正确位置;再使用同样的方法递归地排序划分两部分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
function quickSort(array &$numArr) {
    $len = count($numArr);
    if ($len <= 1) {
        return;
    }
    _quickSort($numArr, 0, $len - 1);
}
 
function _quickSort(array &$numArr, $start, $end) {
    if ($start < $end) {
        $mid = _getMiddle($numArr, $start, $end);
        _quickSort($numArr, $start, $mid - 1);
        _quickSort($numArr, $mid + 1, $end);
    }
}
 
function _getMiddle(array &$numArr, $start, $end) {
    $base = $numArr[$start]; // 基准元素
    while ($start < $end) {
        // 找到比基准元素小的元素位置
        while ($start < $end && $numArr[$end] >= $base) {
            $end--;
        }
        $numArr[$start] = $numArr[$end];
 
        // 找到比基准元素大的元素位置
        while ($start < $end && $numArr[$start] <= $base) {
            $start++;
        }
        $numArr[$end] = $numArr[$start];
    }
    $numArr[$start] = $base;
    return $start;
}

四、归并排序

1、把序列递归地分成短序列,递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换),然后把各个有序的短序列合并成一个有序的长序列,不断合并直到原序列全部排好序;

2、合并过程中我们可以保证如果两个当前元素相等时,我们把处在前面的序列的元素保存在结 果序列的前面,这样就保证了稳定性;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
function mergeSort(array &$numArr) {
    $len = count($numArr);
    if ($len <= 1) {
        return;
    }
    _sort($numArr, 0, $len - 1);
}
 
function _sort(array &$numArr, $start, $end) {
    if ($start < $end) {
        $mid = ($start + $end) >> 1;
        _sort($numArr, $start, $mid);
        _sort($numArr, $mid + 1, $end);
        _merge($numArr, $start, $mid, $end);
    }
}
 
function _merge(array &$numArr, $start, $mid, $end) {
    $left = $start;
    $right = $mid + 1;
    $k = 0;
    $tempArr = [];
 
    // 把较小的元素添加至新数组
    while ($left <= $mid && $right <= $end) {
        if ($numArr[$left] <= $numArr[$right]) {
            $tempArr[$k++] = $numArr[$left++];
        } else {
            $tempArr[$k++] = $numArr[$right++];
        }
    }
 
    // 把左边剩余元素添加至新数组
    while ($left <= $mid) {
        $tempArr[$k++] = $numArr[$left++];
    }
 
    // 把右边剩余元素添加至新数组
    while ($right <= $end) {
        $tempArr[$k++] = $numArr[$right++];
    }
 
    // 新数组中覆盖原数组
    for ($i = 0; $i < $k; $i++) {
        $numArr[$start + $i] = $tempArr[$i];
    }
}

五、基数排序

1、将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零;
2、从最低位开始,依次进行一次排序,每次只比较此位数值;
3、这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列
说明:待排序列长度为n,最高位为d,基数为r(比如10进制的基数为10,16进制基数为16)

发表评论

电子邮件地址不会被公开。 必填项已用*标注