casyup.me@outlook.com

0%

other/sort2

Posted on

this is a follow-up to sort

these sort algorithms based on <Algorithms, 4th>

shell sort

shell sort is a better version sort algorithm based on insert sort.

when a[0] is the biggest number but head of array, for move the number to the end of the array, need swap length(a) elements.

shell sort 是基于插入排序的改良版本

当 a[0] 是整个数组最大的元素时, 为了移动这个元素到数组的尾端, 需要交换 length(a) 次元素. 

1
2
3
4
5
6
7
8
9
10
11
void shellSort(vector<int> &v) {
    int h = 0;
    while (h < v.size() / 3) h = h * 3 + 1;
    while (h >= 1) {
        for (int j = h; j < v.size(); ++j) {
            for (int i = j; i >= h && v[i] < v[i - h]; i -= h)
                swap(v[i], v[i - h]);                         
        }
        h /= 3;
    }
}

bottom-up sort

bottom-up sort is a down-top method based on merge sort.

bottom-up sort 基于合并排序, 是一种从底至上的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void merge(vector<int> &v, int b, int m, int e) {
    vector<int> v2 = v;
    int mid = m++;
    for (int i = b; i <= e; ++i) {
        if (b > mid)
            v[i] = v2[m++];
        else if (m > e)
            v[i] = v2[b++];
        else if (v2[b] < v2[m])
            v[i] = v2[b++];
        else·
            v[i] = v2[m++];
    }
}

void bottomupSort(vector<int> &v) {
	for (int i = 1; i < v.size(); i *= 2){
		for (int j = 0; j < v.size() - i; j = j + 2 * i)
			merge(v, j, j + i -1, min(int(v.size() - 1, j + 2 * i - 1)));
	}
}

a better version of quick sort

if an array with some duplicate numbers, skip these numbers will be more effective

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
#define QS_MIN_LENGTH 7

void quickSort(vector<int> &nums, int b, int e) {
    if (b >= e) return;                          

    // if element too little, insertSort more effective than quickSort
    if (e - b < QS_MIN_LENGTH)
        insertSort(nums, b, e);

    // meduim of three can get more effetive pivot
    int m = (b + e) / 2;
    if (nums[b] > nums[m])
        swap(nums[b], nums[m]);
    if (nums[b] > nums[e])
        swap(nums[b], nums[e]);
    if (nums[m] > nums[e])
        swap(nums[m], nums[e]);

    int pivot = nums[m];
    // skip elements equal pivot
    int lt = b + 1, eq = lt, gt = e - 1;
    while (eq <= gt) { 
        if (nums[eq] < pivot)
            swap(nums[lt++], nums[eq++]);
        else if (nums[eq] > pivot)
            swap(nums[eq], nums[gt--]);
        else
            eq++;
    }       

    quickSort(nums, b, lt - 1);
    quickSort(nums, gt + 1, e);
}

a sort algorithm without compare

I saw a string sort algorithm without compare in <algorithm 4th>. so take some notes

I’m to lazy to write this code, please check the book…