選擇排序:直接選擇排序堆排序 - elvinle－IT工程師數位筆記本

文章出處

上一篇中, 介紹了交換排序中的冒泡排序和快速排序, 那么這一篇就來介紹一下選擇排序和堆排序, 以及他們與快速排序的比較.

一、直接選擇排序

1. 思想

在描述直接選擇排序思想之前, 先來一個假設吧.(先不管這個假設是什么思想的排序啊)

假設我有兩個集合, 一個是待排序集合, 一個是空集合. 現在通過這個空的集合來完成待排序集合的排序.

第一步: 我可以遍歷listA集合, 找到其中最大的數num, 然后把這個num插入到listB中.

listB.Insert(num);

listA.Remove(num);

第二步: 重復第一步的操作, 一直到消耗完 listA 集合中的數.

這樣的話, 數據就逐漸從listA有序的流向了listB. 最后來看listB, 就是一個有序的集合.

代碼如下:

static List<int> InsertSort(List<int> listA)
{
    if (listA == null)
        return null;
    List<int> listB = new List<int>();
    int maxNum = 0;
    int ptr = 0;
    int i = 0;
    while (listA.Count > 0)
    {
        for (i = 0, ptr = 0, maxNum = listA[0]; i < listA.Count; i++)
        {
            if (listA[i] < maxNum)
            {
                maxNum = listA[i];
                ptr = i;
            }
        }
        listB.Add(maxNum);
        listA.RemoveAt(ptr);
    }
　　 listA = listB;
    return listA;
}

直接選擇排序的思想, 與這里的思想是一樣的, 只不過, 不需要使用中間集合來排序, 直接就在自己集合里面做交換就可以了.

接下來, 就來簡化上面的過程, 可以得到直接選擇排序版本:

static List<int> SelectionSort(List<int> list)
{
    int count = list.Count;
    //要遍歷的次數
    for (int i = 0; i < count - 1; i++)
    {
        //假設tempIndex的下標的值最小
        int tempIndex = i;

        for (int j = i + 1; j < count; j++)
        {
            //如果tempIndex下標的值大于j下標的值,則記錄較小值下標j
            if (list[tempIndex] > list[j])
                tempIndex = j;
        }

        //最后將假想最小值跟真的最小值進行交換
        var tempData = list[tempIndex];
        list[tempIndex] = list[i];
        list[i] = tempData;
    }
    return list;
}

2. 復雜度

選擇排序的時間復雜度是O(n²), 乍一看, 怎么和冒泡排序的復雜度是一樣的?

從上面的代碼來看, 選擇排序的循環次數是這樣的:

(n-1) + (n-2) + (n-3) + ... + 2 + 1

結果為 : n²/2

所以, 選擇排序的時間復雜度也是O(n²)

不過, 由于選擇排序需要進行的交換操作很少, 最多的時候, 只會發生n-1次交換,

冒泡排序則是兩兩交換, 最多的時候, 會發生 n²/2次交換. 所以, 選擇排序的性能還是要由于冒泡排序的.

這也是上一篇的, 我會問, 為什么每次都要交換, 而不能找到最大/最小的值, 才進行交換操作.

二、堆排序

1. 思想

1). 前奏

相信很多人都喜歡看籃球比賽, 尤其是nba季候賽, 那么先來看一下, 季后賽是怎么晉級的.

nba季后賽就是這種逐級遞進的方式, 來決定最后的勝者. 在排序中, 我能否借鑒這種形式來排序呢?

1. 看左下角的三個方塊, 有兩個是4級的, 一個是3級的, 假設每個方塊里面都放有一個數, 大小各不同, 那么我是否可以比較這三個數, 然后把其中最大的數, 放到第3級中呢?

2. 如果每三個方塊都可以這樣比較, 那么是否會決出一個最大的值, 放入第1級的這個唯一的一個方塊中呢?

這里面還有一個問題, 如果只有兩個方塊怎么辦呢? 那就只能一個在上, 一個在下, 而不能是兩個在下, 因為需要有一個晉級.

2) 二叉堆

以上的這張圖, 看起來是不是有點熟悉, 感覺有點像二叉樹結構. 在這里, 是二叉堆.

既然要把一組數據映射成為一個二叉堆, 那么就要明白, 這組數據是怎么存儲和映射的.

從上到下, 從左到右的一個順序來映射. 從圖上看, 每一級對應的下標范圍為 : 2ⁿ-1 ~ 2(2ⁿ-1)

接下來就對他進行一輪堆排序: (只需要對父節點進行判斷就可以了)

這里的比較順序: 父節點的比較順序是從下往上, 從有右往左. 且與父節點交換的這個節點還需要與后代節點比較. 以確定他的位置

Demo:

一個父節點的比較, 代碼如下:

static void HeapAdjust(List<int> list, int parent, int length)
{
    //temp保存當前父節點
    int temp = list[parent];

    //得到左孩子的下標(這可是二叉樹的定義，大家看圖也可知道)
    int child = 2 * parent + 1;

    while (child < length)
    {
        //如果parent有右孩子，則要判斷左孩子是否小于右孩子
        if (child + 1 < length && list[child] < list[child + 1])
            child++; //此時的child指向右孩子

        //父親節點大于子節點，就不用做交換
        if (temp >= list[child])
            //這里能這么寫, 就是因為temp節點下的所有節點, 都已經拍過序了, 保證了父節點是子節點中最大的
            break; 

        //將較大子節點的值賦給父親節點
        //這里相當于向前覆蓋, 因為temp已經取出來了, 所以相當于有一個坑可以填數
        list[parent] = list[child];

        //下面就是為下一個循環做準備
        //也就是說, 讓parent指向temp的其中一個大的子節點
        //然后將該子節點做為下一個父節點
        parent = child;

        //找到該新父節點的左孩子節點
        child = 2 * parent + 1;
    }
    //最后將temp值賦給較大的子節點，以形成兩值交換
    list[parent] = temp;
}

接下來就是堆排序的代碼了

///<summary>
/// 堆排序
///</summary>
///<param name="list"></param>
public static void HeapSort(List<int> list)
{
    //list.Count/2-1 就是最后一個父節點的下標, 所有的父節點都是往前放的
    for (int i = list.Count / 2 - 1; i >= 0; i--)
    {
        HeapAdjust(list, i, list.Count);
    }

    //最后輸出堆元素
    for (int i = list.Count - 1; i > 0; i--)
    {
        //堆頂與當前堆的最后一個元素進行值對調
        int temp = list[0];
        list[0] = list[i];
        list[i] = temp;

        //重新塑造堆, 因為堆的最后一個元素會被剔除出去
        //剔除出去的數據, 就是有序的數據
        HeapAdjust(list, 0, i);
    }
}