首頁 > 學院 > 邏輯算法 > 正文

算法系列15天速成 第二天 七大經典排序【中】

2020-10-08 16:14:40
字體:
來源:轉載
供稿:網友

首先感謝朋友們對第一篇文章的鼎力支持,感動中....... 

 

今天說的是選擇排序,包括“直接選擇排序”和“堆排序”。

話說上次“冒泡排序”被快排虐了,而且“快排”贏得了內庫的重用,眾兄弟自然眼紅,非要找快排一比高下。

這不今天就來了兩兄弟找快排算賬。

1.直接選擇排序: 

先上圖:

說實話,直接選擇排序最類似于人的本能思想,比如把大小不一的玩具讓三歲小毛孩對大小排個序,

那小孩首先會在這么多玩具中找到最小的放在第一位,然后找到次小的放在第二位,以此類推。。。。。。

,小孩子多聰明啊,這么小就知道了直接選擇排序。羨慕中........

對的,小孩子給我們上了一課,

第一步: 我們拿80作為參照物(base),在80后面找到一個最小數20,然后將80跟20交換。

第二步:  第一位數已經是最小數字了,然后我們推進一步在30后面找一位最小數,發現自己最小,不用交換。

第三步:........

最后我們排序完畢。大功告成。

既然是來挑戰的,那就5局3勝制。

復制代碼 代碼如下:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
using System.Diagnostics;

namespace SelectionSort
{
    public class Program
    {
        static void Main(string[] args)
        {
            //5次比較
            for (int i = 1; i <= 5; i++)
            {
                List<int> list = new List<int>();

                //插入2w個隨機數到數組中
                for (int j = 0; j < 20000; j++)
                {
                    Thread.Sleep(1);
                    list.Add(new Random((int)DateTime.Now.Ticks).Next(1000, 1000000));
                }

                Console.WriteLine("/n第" + i + "次比較:");

                Stopwatch watch = new Stopwatch();

                watch.Start();
                var result = list.OrderBy(single => single).ToList();
                watch.Stop();

                Console.WriteLine("/n快速排序耗費時間:" + watch.ElapsedMilliseconds);
                Console.WriteLine("輸出前十個數:" + string.Join(",", result.Take(10).ToList()));

                watch.Start();
                result = SelectionSort(list);
                watch.Stop();

                Console.WriteLine("/n直接選擇排序耗費時間:" + watch.ElapsedMilliseconds);
                Console.WriteLine("輸出前十個數:" + string.Join(",", list.Take(10).ToList()));

            }
        }

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

                for (int j = i + 1; j < list.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個父節點(2,,3);

     第二步: 比較2這個父節點的兩個孩子(4,5),發現5大。

     第三步: 然后將較大的右孩子(5)跟父節點(2)進行交換,至此3的左孩子堆構建完畢,

                 如圖:

                         

     第四步: 比較第二個父節點(3)下面的左右孩子(5,1),發現左孩子5大。

     第五步: 然后父節點(3)與左孩子(5)進行交換,注意,交換后,堆可能會遭到破壞,

                 必須按照以上的步驟一,步驟二,步驟三進行重新構造堆。

           

最后構造的堆如下:

                 

 

   第二:輸出大根堆。

             至此,我們把大根堆構造出來了,那怎么輸出呢?我們做大根堆的目的就是要找出最大值,

         那么我們將堆頂(5)與堆尾(2)進行交換,然后將(5)剔除根堆,由于堆頂現在是(2),

         所以破壞了根堆,必須重新構造,構造完之后又會出現最大值,再次交換和剔除,最后也就是俺們

         要的效果了,

 

 

發現自己兄弟被別人狂毆,,堆排序再也坐不住了,決定要和快排干一場。

同樣,快排也不甘示弱,誰怕誰?

復制代碼 代碼如下:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
using System.Diagnostics;

namespace HeapSort
{
    public class Program
    {
        static void Main(string[] args)
        {
            //5次比較
            for (int j = 1; j <= 5; j++)
            {
                List<int> list = new List<int>();

                //插入2w個數字
                for (int i = 0; i < 20000; i++)
                {
                    Thread.Sleep(1);
                    list.Add(new Random((int)DateTime.Now.Ticks).Next(1000, 100000));
                }

                Console.WriteLine("/n第" + j + "次比較:");

                Stopwatch watch = new Stopwatch();
                watch.Start();
                var result = list.OrderBy(single => single).ToList();
                watch.Stop();
                Console.WriteLine("/n快速排序耗費時間:" + watch.ElapsedMilliseconds);
                Console.WriteLine("輸出前十個數" + string.Join(",", result.Take(10).ToList()));

                watch = new Stopwatch();
                watch.Start();
                HeapSort(list);
                watch.Stop();
                Console.WriteLine("/n堆排序耗費時間:" + watch.ElapsedMilliseconds);
                Console.WriteLine("輸出前十個數" + string.Join(",", list.Take(10).ToList()));
            }

        }

        ///<summary>
/// 構建堆
///</summary>
///<param name="list">待排序的集合</param>
///<param name="parent">父節點</param>
///<param name="length">輸出根堆時剔除最大值使用</param>
        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++;

                //父親節點大于子節點,就不用做交換
                if (temp >= list[child])
                    break;

                //將較大子節點的值賦給父親節點
                list[parent] = list[child];

                //然后將子節點做為父親節點,已防止是否破壞根堆時重新構造
                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--)
            {
                //堆頂與當前堆的第i個元素進行值對調
                int temp = list[0];
                list[0] = list[i];
                list[i] = temp;

                //因為兩值交換,可能破壞根堆,所以必須重新構造
                HeapAdjust(list, 0, i);
            }
        }
    }
}

結果公布:

堆排序此時心里很尷尬,雙雙被KO,心里想,一定要撈回面子,一定要贏,

于是堆排序提出了求“前K大問題”。(就是在海量數據中找出前幾大的數據),

快排一口答應,小意思,沒問題。

雙方商定,在2w隨機數中找出前10大的數:

復制代碼 代碼如下:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
using System.Diagnostics;

namespace QuickSort
{
    public class Program
    {
        static void Main(string[] args)
        {
            //5此比較
            for (int j = 1; j <= 5; j++)
            {
                List<int> list = new List<int>();

                for (int i = 0; i < 20000; i++)
                {
                    Thread.Sleep(1);
                    list.Add(new Random((int)DateTime.Now.Ticks).Next(1000, 100000));
                }

                Console.WriteLine("/n第" + j + "次比較:");

                Stopwatch watch = new Stopwatch();
                watch.Start();
                var result = list.OrderByDescending(single => single).Take(10).ToList();
                watch.Stop();
                Console.WriteLine("/n快速排序求前K大耗費時間:" + watch.ElapsedMilliseconds);
                Console.WriteLine("輸出前十個數:" + string.Join(",", result.Take(10).ToList()));

                watch = new Stopwatch();
                watch.Start();
                result = HeapSort(list, 10);
                watch.Stop();
                Console.WriteLine("/n堆排序求前K大耗費時間:" + watch.ElapsedMilliseconds);
                Console.WriteLine("輸出前十個數:" + string.Join(",", list.Take(10).ToList()));
            }

        }

        ///<summary>
/// 構建堆
///</summary>
///<param name="list">待排序的集合</param>
///<param name="parent">父節點</param>
///<param name="length">輸出根堆時剔除最大值使用</param>
        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++;

                //父節點大于子節點,不用做交換
                if (temp >= list[child])
                    break;

                //將較大子節點的值賦給父親節點
                list[parent] = list[child];

                //然后將子節點做為父親節點,已防止是否破壞根堆時重新構造
                parent = child;

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

        ///<summary>
/// 堆排序
///</summary>
///<param name="list">待排序的集合</param>
///<param name="top">前K大</param>
///<returns></returns>
        public static List<int> HeapSort(List<int> list, int top)
        {
            List<int> topNode = new List<int>();

            //list.Count/2-1:就是堆中非葉子節點的個數
            for (int i = list.Count / 2 - 1; i >= 0; i--)
            {
                HeapAdjust(list, i, list.Count);
            }

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

                //最大值加入集合
                topNode.Add(temp);

                //因為順序被打亂,必須重新構造堆
                HeapAdjust(list, 0, i);
            }
            return topNode;
        }
    }
}

求前K大的輸出結果:

最后堆排序趕緊拉著直接選擇排序一路小跑了,因為求前K大問題已經不是他原本來的目的。

ps: 直接選擇排序的時間復雜度為:O(n^2)

       堆排序的時間復雜度:O(NlogN)

發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
金玫玫床戏