[c++] [python] 排序

作者: cca1yy | 来源:发表于2019-10-12 23:45 被阅读0次

写在前面：面试官经常会要求应聘者比较插入排序、冒泡排序、归并排序、快速排序等不同算法的优劣。一定要对各种排序算法的特点烂熟于胸，能够从额外空间消耗、平均时间复杂度、最差时间复杂度等方面比较它们的优缺点。

要能够熟练写出快速排序的代码。

各种排序算法的复杂度和稳定性分析：
一般二分的复杂度都跟logn有关（即log(2^n)）
稳定性，就是有两个相同的元素，排序先后的相对位置是否变化，主要用在排序时有多个排序规则的情况下。

快速排序：平均o(nlogn); 最坏o(n^2).
最好的情况：每次寻找到的基准数都能把数组一分为二，T(n) = 2*T(n/2) + o(n)，即T(n) = o(nlogn)；最坏情况：每次寻找到的基准数都是无序区中最小或最大的元素，划分之后的自数字只比之前少一个数。T(n) = o(n) + T(n-1).即为T(n) = o(n^2). 由于每次都需要和中轴元素交换，因此原来的顺序就可能被打乱。如序列为 5 3 3 4 3 8 9 10 11会将3的顺序打乱。所以说，快速排序是不稳定的！
归并排序：总是o(nlogn)
一趟归并需要n次，总共需要logn次。稳定的排序算法，归并过程中不会改变相等元素的相对位置。但是需要额外的o(n)空间。
冒泡排序：平均和最坏o(n^2)；最好o(n); 空间复杂度保持o(1)。
最好情况：正序有序（从小到大），只需比较n次；最坏情况：逆序有序，则需比较(n-1)+(n-2)+(n-3)+....+1, 故为o(n^2).
插入排序：平均和最坏o(n^2);最好o(n).
最好情况：正序有序（从小到大），只需比较n次，不需移动；最坏情况：逆序有序（从大到小），每个元素都需要比较n次，共有n个元素。在插入排序中，K1是已排序部分中的元素，当K2和K1比较时，直接插到K1的后面(没有必要插到K1的前面，这样做还需要移动！！)，因此，插入排序是稳定的。

image.png

1. 快速排序(挖坑填数+分治法，类似二分与递归，快排序的平均和最好情况下时间复杂度是O(nlogn), 最坏情况下为O(n^2)，空间复杂度是O(l0gn)，因为快排的实现是递归调用的，而且每次函数调用中只使用了常数的空间，因此空间复杂度等于递归深度O(l0gn)--这是比较好的情况，若最差的情况，每次选的基准数都只能将数组分成1，和 n - 2大小的两个数组，则空间复杂度为O(n))

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。

该方法的基本思想是：
1．先从数列中取出一个数作为基准数。
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3．再对左右区间重复第二步，直到各区间只有一个数。

对挖坑填数进行总结:
1．i =L; j = R; 将基准数挖出形成第一个坑a[i]。//L为数组起始下标0，R为数组终止下标。第一个坑a[i]为选定的基准数。设X = a[i]。
2．j--由后向前找比X小的数，找到后挖出此数填前一个坑a[i]中。
3．i++由前向后找比X大的数，找到后也挖出此数填到前一个坑a[j]中。
4．再重复执行2，3二步，直到i==j，将基准数X填入a[i]中。//此时a[i] = X,并且a[i]之前的数都小于a[i], a[i]之后的数都大于a[i]。

具体实例

image.png
第4步结束之后，相当于以a[5] = a[i]为中介，将整个数组分为了[l, i - 1]和[i + 1, r]两部分，再对左右两部分重复图中的操作。

C++代码--采用了递归的思想

// test0304_1.cpp : 定义控制台应用程序的入口点。
//

// 快速排序
#include "stdafx.h"
#include <iostream>
using namespace std;

void AdjustArray(int s[], int l, int r)
{
    if (l < r) //控制递归的次数
    {
        int i = l;
        int j = r;
        int X = s[i];
        while (i < j) //直到 i == j, 一次挖坑填数结束
        {
            while (i < j && s[j] >= X)
                j--;
            if (i < j)
            {
                s[i] = s[j];
                i++;
            }

            while (i < j && s[i] < X)
                i++;
            if (i < j)
            {
                s[j] = s[i];
                j--;
            }
        }
        s[i] = X; //此时，s[i]左边的数都小于它，右边的数都大于它。之后采用递归法分别对左右两部分数排序，直到参数中l == r.
        AdjustArray(s, l, i - 1);
        AdjustArray(s, i + 1, r);
    }
}


int main()
{
    int s[] = {72, 6, 57, 88, 60, 42, 83, 73, 48, 85};
    int len = sizeof(s) / sizeof(s[0]);
    cout << "排序前的数组为：";
    for (int i = 0; i < len; i++)
    {
        cout << s[i] << " ";
    }
    cout << endl;

    AdjustArray(s, 0, len - 1);

    cout << "排序后的数组为：";
    for (int i = 0; i < len; i++)
    {
        cout << s[i] << " ";
    }
    cout << endl;
    return 0;
}

运行结果

python代码

# quickSort.py

def quickSort(inputArray, left, right):
    i = left
    j = right
    if i < j:
        baselineNum = inputArray[i] #取最左边的数作为基准数
        while i < j: # i 和 j不断变化，直到i == j，一次挖坑填数结束
            while i < j and inputArray[j] >= baselineNum: #这里对于i < j的判断非常重要，在j不断减少的过程中，要保证j始终大于i，否则应该立即退出此次挖坑填数
                j -= 1
            if i < j: # 若找到比基准数更小的数，则将该数填到坑里
                inputArray[i] = inputArray[j]
                i += 1
            while i < j and inputArray[i]  <= baselineNum:
                i += 1
            if i < j:
                inputArray[j] = inputArray[i]
                j -= 1
        inputArray[i] = baselineNum # 此时 i == j
        quickSort(inputArray, left, i - 1) # 对基准数左边的部分再次进行挖坑填数
        quickSort(inputArray, i + 1, right) # # 对基准数右边的部分再次进行挖坑填数

if __name__ == "__main__":
    inputArray = [72, 6, 57, 88, 60, 42, 83, 73, 48, 85]
    print("input array = ", inputArray)
    quickSort(inputArray, 0, len(inputArray) - 1)
    print("sorted array = ", inputArray)

代码运行结果

2. 冒泡排序(插入排序和冒泡排序在平均和最坏情况下的时间复杂度都是 O(n^2)，最好情况下都是 O(n)，空间复杂度是 O(1)。 )

算法基本思想
冒泡排序是非常容易理解和实现，，以从小到大排序举例：
设数组长度为N。
1．比较相邻的前后二个数据，如果前面数据大于后面的数据，就将二个数据交换。
2．这样对数组的第0个数据到N-1个数据进行一次遍历后，最大的一个数据就“沉”到数组第N-1个位置。
3．N=N-1，如果N不为0就重复前面二步，否则排序完成。
c++ 代码一

// test0304_4.cpp : 定义控制台应用程序的入口点。
//

//冒泡排序的基本实现;
#include "stdafx.h"
#include <iostream>
using namespace std;

void swap(int &x, int &y)
{
    int tmp;
    tmp = x;
    x = y;
    y = tmp;
}

void BubblingSort(int a[], int n)//n为数组a的长度，此函数为冒泡排序的算法
{
    for(int i = 0; i < n; i++) //控制每次交换的末尾节点，n-1, n-2, n-3....,因为每排序一次，最大的那个数都沉到排序数组的末尾。
    {
        for (int j = 1; j < n - i; j++)
        {
            if (a[j - 1] > a[j]) swap(a[j - 1], a[j]);
        }
    }
}


int main()
{
    int a[] = { 1, 2, 4, 90, 45, 30, 22, 11, 39 };
    cout << " 排序前的数组为：" << endl;
    for (int i = 0; i < 9; i++) cout << a[i] << " ";
    cout << endl;
    BubblingSort(a, 9);
    cout << " 排序后的数组为：" << endl;
    for (int i = 0; i < 9; i++) cout << a[i] << " ";
    cout << endl;
    return 0;
}

运行结果

c++ 代码二
下面对其进行优化，设置一个标志，如果这一趟发生了交换，则为true，否则为false。明显如果有一趟没有发生交换，说明排序已经完成。

// test0304_5.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
using namespace std;

void swap(int &x, int &y)
{
    int tmp;
    tmp = x;
    x = y;
    y = tmp;
}

void BubblingSort(int s[], int n)
{
    bool flag = true;
    int k = n;
    while (flag)
    {
        flag = false;
        for (int j = 1; j < k; j++)
        {
            if (s[j - 1] > s[j])
            {
                swap(s[j - 1], s[j]);
                flag = true;
            }
        }
        k--;
    }
}


int main()
{
    int a[] = { 1, 2, 4, 90, 45, 30, 22, 11, 39 };
    cout << " 排序前的数组为：" << endl;
    for (int i = 0; i < 9; i++) cout << a[i] << " ";
    cout << endl;
    BubblingSort(a, 9);
    cout << " 排序后的数组为：" << endl;
    for (int i = 0; i < 9; i++) cout << a[i] << " ";
    cout << endl;
    return 0;
}

运行结果

python代码

# bubbleSort.py

def bubbleSort(inputArray, length):
    flag = False #设置一个flag，在数组已经有序的情况下，尽快退出程序，避免无谓的资源消耗
    for i in range(length - 1, -1, -1):
        for j in range(i):
            if inputArray[j] > inputArray[j + 1]:
                temp = inputArray[j + 1]
                inputArray[j + 1] = inputArray[j]
                inputArray[j] = temp
                flag = True # 在一次冒泡排序的过程中，只要有一次数据交换，就说明数组没有完全有序，需要接着进行下一轮冒泡排序
        if flag == False: 
            return
if __name__ == "__main__":
    inputArray = [72, 6, 57, 88, 60, 42, 83, 73, 48, 85]
    print("input array = ", inputArray)
    bubbleSort(inputArray, len(inputArray))
    print("sorted array = ", inputArray)

代码运行结果

3. 插入排序(最好情况o(n)-数组已经有序，只需让a[i]与前一个元素a[i-1]比较；最坏情况，从i =1并且逐步增加开始，每次都要与前面的所有元素进行比较，则操作次数为1,2,3,4...(n-1),时间复杂度为o(n^2))

直接插入排序(Insertion Sort)的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。

如下图所示，每次选择一个元素K插入到之前已排好序的部分A[1…i]中，插入过程中K依次由后向前与A[1…i]中的元素进行比较。若发现A[x]<=K,则将K插入到A[x]的后面，插入前需要移动元素。

插入排序示意图

设数组为a[0…n-1]。

初始时，a[0]自成1个有序区，无序区为a[1..n-1]。令i=1
将a[i]并入当前的有序区a[0…i-1]中形成a[0…i]的有序区间。
i++并重复第二步直到i==n-1。排序完成。

// insertionSort.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
using namespace std;


void Insertsort1(int a[], int n)
{
    int i, j, k;
    for (i = 1; i < n; i++)
    {
        //为a[i]在前面的a[0...i-1]有序区间中找一个合适的位置
        for (j = i - 1; j >= 0; j--)
            if (a[j] < a[i]) //若找到小于a[i]的元素a[j]，则应该将a[i]放置到a[j+1]
                break;

        //如找到了一个合适的位置
        if (j != i - 1) //若a[i - 1] < a[i],则到a[i]为止数组都是有序的，不用换顺序 
        {
            //将比a[i]大的数据向后移
            int temp = a[i];
            for (k = i - 1; k > j; k--)
                a[k + 1] = a[k];
            //将a[i]放到正确位置上
            a[k + 1] = temp;
        }
    }
}

void Insertsort2(int a[], int n)
{
    int j;
    for (int i = 1; i < n; i++)
    {
        if (a[i] < a[i - 1])
        {
            int tmp = a[i];
            for (j = i - 1; j >= 0 && a[j] >= tmp; j--) //控制条件很重要
            {
                a[j + 1] = a[j];
            }
            a[j + 1] = tmp;
        }
    }
}

void Insertsort3(int a[], int n)//此方法最好
{
    int i, j;
    for (int i = 1; i < n; i++)
    {
        for (j = i - 1; j >= 0 && a[j] > a[j + 1]; j--) //从a[j = i - 1]向前遍历，若a[j] > a[j + 1],则将a[j]与a[j + 1]交换位置，直到a[j] <= a[j + 1];若a[j] <= a[j - 1],说明前面都是有序的
            swap(a[j], a[j + 1]);
    }
}

int main()
{
    int a[] = {9,7,5,6,1,18,35,21,8};
    int n = sizeof(a) / sizeof(a[0]);
    cout << "排序前的数组：" << endl;
    for (int i = 0; i < n; i++)
        cout << a[i] << " ";
    cout << endl;
    Insertsort3(a, n);
    //insertionSort(a, n);
    cout << "排序后的数组：" << endl;
    for (int j = 0; j < n; j++)
        cout << a[j] << " ";
    cout << endl;
    return 0;
}

python代码

# insertionSort.py

def insertionSort(inputArray, length):
    for i in range(1, length):
        j = i - 1
        while j >= 0 and inputArray[i] <= inputArray[j]:
            j -= 1
        if j != i - 1: #i之前的[0, j]已经是有序的，因此若inputArray[i] > inputArray[i - 1],则不用换顺序
            temp = inputArray[i] #退出while循环表示，当前插入元素inputArray[i]遇到比它小的元素inputArray[j]了，应把inputArray[i]插入到inputArray[j]后面
            for k in range(i - 1, j, -1): 
                inputArray[k + 1] = inputArray[k] #将 [j + 1] ~ [i - 1]都向后移一位
            inputArray[j + 1] = temp #把inputArray[i]插入到inputArray[j]后面

if __name__ == "__main__":
    inputArray = [72, 6, 57, 88, 60, 42, 83, 73, 48, 85]
    print("input array = ", inputArray)
    insertionSort(inputArray, len(inputArray))
    print("sorted array = ", inputArray)

代码运行结果

4. 归并排序（类似二分和递归，归并排序的好处就是时间复杂度总是O(nlogn)）

归并排序就是每次都将数组一分为二，直到将数组都分成单个元素的子数组，然后进行排序，一层一层向上和自己同级的元素按顺序合并。这个是要额外借助两个数组L[]和R[]来存储子数组，额外的两个数组初始化时分别是左右两个数组的长度。具体过程看看下图吧。

归并排序具体过程

c++代码

// mergesort.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
using namespace std;

void Merge(int* A, int* L, int leftCount, int* R, int rightCount) //将传入的两个子数组L和R使用两个指针排序，并按照顺序将元素存入A中
{
    //cout << "Merge L:" << L[0] << " " <<"leftCount:" << leftCount << " " << "Merge R:" << R[0] <<" "<< "rightCount:" << rightCount <<endl;
    int i = 0, j = 0, k = 0; //i用来指向L数组中元素的位置，j用来指向R数组中元素的位置，K用来指向A数组中元素的位置
    //此处一定要用while，而不是if
    while (i < leftCount && j < rightCount) //若L和k中都有剩余元素，则比较L和R中相应元素的大小，将小的数存入A；若不满足此条件，则证明L或R中至少有一个数组的元素都已经比较完了
    {
        if (L[i] <= R[j]) { A[k] = L[i]; k++; i++;}
        if (L[i] > R[j]) { A[k] = R[j]; k++; j++;}
    }
    /*
    if (i < leftCount) //若L中还有剩余元素，表明R中已经没有剩余元素了，则将L中剩余的元素都赋值到A数组中，至此，带有排序功能的归并结束
    {
        for (int a = i; a < leftCount; a++)
        {
            A[k] = L[a];
            k++;
        }
    }
    if(j < rightCount)
        for (int b = j; b < rightCount; b++)
        {
            A[k] = R[b];
            k++;
        }
        */
    while (i < leftCount) { A[k] = L[i]; k++; i++;}
    while (j < rightCount) { A[k] = R[j]; k++; j++;}
    /*
    cout << "当前merge的数组为：";
    for (int c = 0; c < k; c++)
    {
        cout << A[c] << " ";
    }
    cout << endl;
    */
}


void MergeSort(int* A, int n) //不断二分以构造两个子数组
{
    //cout << "A=" << A[0] << " "<< "mid = " << n << endl;
    if (n < 2) return; //若待排序数组长度小于2，则不用做任何操作,这也是递归的终止条件

    int mid = n / 2; //取数组的中间位置
    int *L = new int[mid]; //新建一个数组中mid左半部分长度的数组，以存储左半部分的数组元素
    int *R = new int[n - mid]; //新建一个数组中mid右半部分长度的数组，以存储右半部分的数组元素

    for (int i = 0; i < mid; i++) { L[i] = A[i];} ////将数组mid左半部分的元素存储到L[]里
    for (int i = mid; i < n; i++) R[i - mid] = A[i]; //将数组mid右半部分的元素存储到R[]里

    MergeSort(L, mid);
    MergeSort(R, n - mid);
    Merge(A, L, mid, R, n - mid);

    delete[] R; //为R和L分配的内存需要释放掉
    delete[] L;
}


int main()
{
    int A[] = { 6,2,3,1,9,10,15,13,12,17 };
    int n = sizeof(A) / sizeof(A[0]);
    cout << "原始数组：";
    for (int i = 0; i < n; i++)
    {
        cout << A[i] << " ";
    }
    cout << endl;
    MergeSort(A, n);
    cout << "归并排序后的数组：";
    for (int j = 0; j < n; j++)
    {
        cout << A[j] << " ";
    }
    cout << endl;
    return 0;
}

可算调出结果了，while和if一定不要混用啊，需要多次循环的一定要用while!!!

可以通过这个运行结果来看看归并排序递归调用的整个过程呀

python代码，下例使用长度为8的数组打印递归过程，便于理解

# mergeSort.py

def mergeSort(inputArray, n): # 通过递归的方法，类似于二分法将数组分成L和R两个子数组
    print("mergeSort(", inputArray, ",", n, ") called!")
    if (n < 2):
        return
    mid = n // 2
    L = [0] * mid
    R = [0] * (n - mid)
    for i in range(0, mid):
        L[i] = inputArray[i]
    for j in range(mid, n):
        R[j - mid] = inputArray[j]

    mergeSort(L, mid) # 一直划分最左边的数组，直到划分后的L长度为1为止，接着调用下一句mergeSort(R, n - mid)
    mergeSort(R, n - mid) # 此时的R和上一句最终的L一致，都是长度为1的位置，因此运行一次结束，马上调用下一个merge函数
    merge(inputArray, L, mid, R, n - mid)

def merge(inputArray, L, leftCount, R, rightCount): # 对于每个划分后的
    print("merge(", inputArray, ",", L, ",", leftCount, ",", R, ",", rightCount, ") called!")
    i = 0
    j = 0
    k = 0
    while i < leftCount and j < rightCount: # 这层while循环，是从L和R两个数组内选取较小的数存入inputArray中
        print("i = ", i, ", j = ", j)
        if L[i] <= R[j]:
            inputArray[k] = L[i]
            k += 1
            i += 1
        else:
            inputArray[k] = R[j]
            k += 1
            j += 1
    while i < leftCount: # 若R中的元素都已经存入inputArray中，说明L中剩余的元素都比R中元素大，直接存入inputArray中邻接的位置即可
        inputArray[k] = L[i]
        k += 1
        i += 1
    while j < rightCount:
        inputArray[k] = R[j]
        k += 1
        j += 1

if __name__ == "__main__":
    #inputArray = [72, 6, 57, 88, 60, 42, 83, 73, 48, 85]
    inputArray = [6, 2, 3, 1, 9, 10, 15, 13]
    print("input array = ", inputArray)
    mergeSort(inputArray, len(inputArray))
    print("sorted array = ", inputArray)

代码运行结果，配合下图理解整个二分及归并的过程

拆分过程为红色，归并过程为蓝色

所以每次mergeSort(L, mid)递归完成之后，都可以根据根节点，顺利找到相应的R数组？？

5. 堆排序

二叉堆是完全二叉树或者是近似完全二叉树。二叉堆包含最大堆和最小堆。由于其它几种堆（二项式堆，斐波纳契堆等）用的较少，一般将二叉堆简称为堆。

最大堆满足如下两个特性：

父结点的键值总是大于或等于任何一个子节点的键值
每个结点的左子树和右子树都是一个最大堆

最小堆满足如下两个特性：

父结点的键值总是小于或等于任何一个子节点的键值
每个结点的左子树和右子树都是一个最小堆

一般都用数组来存储堆，从堆的根节点开始，从上到下，从左到右地将节点值存入数组。因此 i 结点的父结点下标就为(i – 1) / 2。它的左右子结点下标分别为2 * i + 1和2 * i + 2。如第0个结点左右子结点下标分别为1和2。

堆排序python代码

总之堆排序分为三个步骤：
1). 将待排序数组 inputArray 构造为一颗完全二叉树binaryTree。
2). 按照排序的需求，将该完全二叉树binaryTree调整为最大堆或者最小堆。若需要将inputArray升序排序，则应将完全二叉树binaryTree的根节点调整为最大值，即binaryTree调整为最大堆；反之，若需要降序排序，则应将完全二叉树binaryTree调整为最小堆。（调整过程是从最后一个非叶子节点开始(n - 1) // 2，调整以每个非叶子节点为根节点的子树，直到调整到整个完全二叉树binaryTree的根节点，在数组中的下标为0。）这里要注意的一点是，每次调整完一颗子树a为最大堆或者最小堆之后，要检查子树a的子树b是否仍然满足最大堆或者最小堆，若不满足，要调整子树b及子树b的子树，直到调整到叶子节点。
3). 将完全二叉树binaryTree的根节点与树中最后一个节点交换位置（树中交换位置之后，删掉最后一个元素（即交换过来的根节点）），重新调整为最大堆或者最小堆，然后将binaryTree的根节点与树中最后一个节点交换位置，再调整，重复直到只剩一个节点。

# heapSort.py
# 堆排序(升序，最大堆)

# 长度为n的数组中，将 以i为根节点的子树调整为最大堆
# 注意这里，调整完 以i为根节点的子树 之后，若该子树的子节点和根节点有位置变动，还需要考虑变动后子节点的子树调整
def heapify(inputArray, n, i):
    # inputArray: 待排序的数组
    # n：待排序数组inputArray的长度
    # i：待调整子树的根节点，其子节点分别为 2 * i + 1, 2 * i + 2
    largestNum = i # 保存待调整子树的最大值下标
    left = 2 * i + 1 # 根节点 i 的左子节点
    right = 2 * i + 2 # 根节点 i 的右子节点

    # 若 根节点 i 的左子节点存在，且左子节点取值比根节点更大，则将待调整子树的最大值下标设置为左子节点
    if left < n and inputArray[left] > inputArray[i]:
        largestNum = left
    # 若 根节点 i 的右子节点存在，且右子节点取值比(左子节点和根节点取值的最大值)更大，则将待调整子树的最大值下标设置为右子节点
    if right < n and inputArray[right] > inputArray[largestNum]:
        largestNum = right

    if largestNum != i: # 若 检查出的 待调整子树 的最大取值不是根节点的取值，则交换 i 和 largestNum的位置
        inputArray[i], inputArray[largestNum] = inputArray[largestNum], inputArray[i]
        # 交换位置之后，还要继续调整以largestNum下标为根节点的子树，直到叶子节点
        heapify(inputArray, n, largestNum)
        '''
        # 每次调整一个小三角的根节点之后，将子节点的最大值调整到根节点，因此现在子节点的值比原来小
        # 那么又要调整以 如今更小值的子节点 为根节点的子树，相当于从上往下调整
        '''

# 依照堆排序的三个步骤，写代码。
'''
1) 将数组构造成完全二叉树
2) 根据升序/降序的要求，将完全二叉树调整为最大堆/最小堆
3) 将根节点与最后一个节点交换位置，删除交换后的最后一个节点(即原根节点值)，重新调整，再交换，再调整
'''
def heapSort(inputArray):
    n = len(inputArray)
    indexLastMiddleNode = (n - 1) // 2 #最后一个非叶子节点的位置
    for i in range(indexLastMiddleNode, -1, -1):
        heapify(inputArray, n, i) # 2) 将完全二叉树调整为最大堆

    # 3) 交换位置，删除，重新调整
    for j in range(n - 1, 0, -1):
        inputArray[0], inputArray[j] = inputArray[j], inputArray[0] 
        # 将 最大堆 的根节点与最后一个节点交换位置，即将数组最大值调整到最后
        heapify(inputArray, j, 0) # 从上往下将二叉树调整为大顶堆
  
arr = [ 12, 11, 13, 5, 6, 7] 
heapSort(arr) 
n = len(arr) 
print ("排序后") 
for i in range(n): 
    print ("%d" %arr[i])

代码运行结果

6. 直接选择排序

直接选择排序和直接插入排序类似，都将数据分为有序区和无序区，所不同的是直接插入排序是将无序区的第一个元素直接插入到有序区以形成一个更大的有序区，而直接选择排序是从无序区选一个最小的元素直接放到有序区的最后。

算法步骤如下：(设数组为a[0, 1, ..., n-1]。)

初始时，数组 a[0, 1, ..., n-1] 全为无序区。 $\color{blue}{算法开始，令i=0}$
在无序区 a[i, i+1, …, n-1] 中选取一个最小的元素，将其与 a[i] 交换。交换之后a[0, …, i]就形成了一个有序区。
i++并重复第二步直到i==n-1。排序完成。

python代码

# selectiveSort.py

def selectiveSort(inputArray, length):
    for i in range(length): # 遍历数组inputArray的每一个下标为i的位置，该位置都应该是[i, length - 1]位置上元素的最小值
        minIndex = i
        for j in range(i, length):
            if inputArray[j] < inputArray[minIndex]: # 遍历 i 及其之后的元素，选择最小的元素，将其与inputArray[i]交换位置
                minIndex = j
        temp = inputArray[minIndex]
        inputArray[minIndex] = inputArray[i]
        inputArray[i] = temp

if __name__ == "__main__":
    inputArray = [72, 6, 57, 88, 60, 42, 83, 73, 48, 85]
    print("input array = ", inputArray)
    selectiveSort(inputArray, len(inputArray))
    print("sorted array = ", inputArray)

代码运行结果

7. 希尔排序

参考

白话经典算法系列之六快速排序快速搞定：https://blog.csdn.net/MoreWindows/article/details/6684558
白话经典算法系列之一冒泡排序的三种实现：https://blog.csdn.net/MoreWindows/article/details/6657829
白话经典算法系列之五归并排序的实现：https://blog.csdn.net/MoreWindows/article/details/6678165
https://blog.csdn.net/a130737/article/details/38228369 --这个归并排序也讲解地很清楚
白话经典算法系列之二直接插入排序的三种实现：https://blog.csdn.net/MoreWindows/article/details/6665714
白话经典算法系列之七堆与堆排序：
https://blog.csdn.net/morewindows/article/details/6709644
白话经典算法系列之八 MoreWindows白话经典算法之七大排序总结篇：https://blog.csdn.net/MoreWindows/article/details/7961256
常见排序算法小结: https://blog.csdn.net/whuslei/article/details/6442755
图解排序算法(三)之堆排序
 Python 堆排序

[c++] [python] 排序

2. 冒泡排序(插入排序和冒泡排序在平均和最坏情况下的时间复杂度都是 O(n^2)，最好情况下都是 O(n)，空间复杂度是 O(1)。 )

3. 插入排序(最好情况o(n)-数组已经有序，只需让a[i]与前一个元素a[i-1]比较；最坏情况，从i =1并且逐步增加开始，每次都要与前面的所有元素进行比较，则操作次数为1,2,3,4...(n-1),时间复杂度为o(n^2))

4. 归并排序（类似二分和递归，归并排序的好处就是时间复杂度总是O(nlogn)）

5. 堆排序

6. 直接选择排序

7. 希尔排序

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读