FLAMEc隨手記

一陣風飄過~~~

0%

Tim排序法

發表於 更新於

是leetcode的題目，題目如下(直接複製的)：

Given an array of integers nums, sort the array in ascending order and return it.

You must solve the problem without using any built-in functions in O(nlog(n)) time complexity and with the smallest space complexity possible.

心得：

簡單說大概就是自己寫排序不要用已經有的排序吧!!

一開始我是用較常用的排序法QuickSort就上了!!!

結果超時!!!!!!!!!

結果超時!!!!!!!!!

猜測大概是會排序到對QuickSort來說最壞狀況的陣列，剛好超時吧!?

所以稍微找了一下更快的排序法~

  1. MergeSort 合併排序法
  2. TimSort Tim排序法

研究後發現兩者有一定關係，TimSort像是MergeSort優化版本，或著說加強版。

TimSort會將數列分割成一定大小，然後先用InsertSort排序，之後才開始用MergerSort合併。

最後實作如下：

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
class Solution {
public:
    //插入排序法，小數量很穩
    void insertSort(vector<int>& nums,int left , int right)
    {
        for(int i = left + 1; i <= right; i++)
        {
            int val = nums[i];
            int j = i - 1;
            while(j >= left && nums[j] > val)
            {
                nums[j+1] = nums[j];
                j--;
            }
            nums[j+1] = val;
        }
    }

    //MergeSort，看網上TimSort資料這邊也有優化，似乎把一個一個檢查改成跳幾個檢查
    void merge(vector<int>& nums,vector<int>& cpyBuff,int left , int mid , int right)
    {
        int leftn = 0,rightn;
        for(int i = left; i <= mid; i++)
        {
            cpyBuff[leftn] = nums[i];
            leftn++;
        }

        int len = mid - left;
        leftn = 0;
        rightn = mid + 1;
        //兩個排序數列找小的放前面
        while(leftn <= len && rightn <= right)
        {
            if(cpyBuff[leftn] > nums[rightn])
            {
                nums[left] = nums[rightn];
                rightn++;
                left++;

            }
            else
            {
                nums[left] = cpyBuff[leftn];
                leftn++;
                left++;
            }
        }

        while(leftn <= len)
        {
            nums[left] = cpyBuff[leftn];
            leftn++;
            left++;
        }

        while(rightn <= right)
        {
            nums[left] = nums[rightn];
            rightn++;
            left++;
        }
    }

    vector<int> sortArray(vector<int>& nums) {
        int n = nums.size();
        int run = 32; //分割大小，稱為Run
        for(int i = 0 ; i < n; i += run)
            insertSort(nums,i,std::min(n - 1 , i + run - 1));

        int cpySize = run;
        while(cpySize < n)
        {
            cpySize *= 2;
        }
        cpySize = cpySize >> 1;
        std::vector<int> cpyBuff(cpySize);
        for(int size = run; size < n ; size *= 2)
        {
            for(int i = 0; i < n; i += size * 2)
            {
                int mid = i + size - 1;
                if(mid >= n)
                    continue;
                int right = std::min(n - 1 , mid + size);

                merge(nums,cpyBuff,i,mid,right);
            }
        }

        return nums;
    }
};