Sort Algorithms 整理

发表于 | 分类于

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void BubbleSort(int a[], int n) {
    bool flag = false; //标记是否发生交换，若没有表示已经有序
    for (int i = 0; i < n-1; ++i) { //要进行n-1次冒泡
        for (int j = n-1; j > i; j--) { 
            /* 
            从最后一个元素开始，较小的在前
            */
            if (a[j] < a[j-1]) {
                int tmp = a[j-1];
                a[j-1] = a[j];
                a[j] = tmp;
                flag = true;
            }
        }
        if (flag == 0) {
            return;
        }
    }
}

两端同时开始比较交换，衍生出双向冒泡算法

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
void DbubbleSort(int a[], int n) {
    int i = 1, j = 0;
    bool noswap = true;
    while (noswap) { //当没有发生交换时，表示有序
        noswap = false;
        /* 
            从最后一个元素开始到第一个元素，较小的在前
            从倒数每二个元素开始到第二个元素 ...
            ...
            */
        for (j = n-i; j >= i; --j) {
            if (a[j] < a[j-1]) {
                int tmp = a[j];
                a[j] = a[j-1];
                a[j-1] = tmp;
                noswap = true;
            }
        }
        /* 
            从第二个元素开始到倒数第二个元素，较大的在后
            从第三个元素开始倒数第三个元素 ...
            ...
            */
        for (j = i; j <= n-i-1; ++j) {
            if (a[j] > a[j+1]) {
                int tmp = a[j];
                a[j] = a[j+1];
                a[j+1] = tmp;
                noswap = true;
            }
        }
        ++i;
    }
}

插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void InsertSort(int a[], int n) {
    /* 
    第二个元素开始,与第一个元素比较，若第一个元素大，则交换
    第三个元素，与前面二个元素比较，逐个向后移一位，直到找到比该元素小的元素为止
    ...
    */
    for (int i = 1; i < n; ++i) { 
        int min = a[i];
        int j = i-1;
        for (; min < a[j]; j--) {
            a[j+1] = a[j];
        }
        a[j+1] = min;
    }
}

希乐排序

分成多个增量，依次按增量进行插入排序，但最后一个增量必须是1，如：5,3,1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
static void ShellInsert(int a[], int dk, int n) { //dk为当前增量
    for (int i = dk; i < n; ++i) {
        int min = a[i];
        int j = i-dk;
        for (; j >= 0 && min < a[j]; j -= dk) {
            a[j+dk] = a[j];
        }
        a[j+dk] = min;
    }
}

void ShellSort(int a[], int d[], int t, int n) {
    for (int k = 0; k < t; ++k) {
        ShellInsert(a, d[k], n);
    }
}

直接选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void SelectSort(int a[], int n) {
    /*
        从第一个元素开始到最后一个，找到第小元素与第一个元素交换
        从第二个元素开始 ...
        ...
    */
    for (int i = 0; i < n-1; ++i) {
        int k = i;
        for (int j = i+1; j < n; ++j) {
            if (a[j] < a[k]) {
                k = j;
            }
        }
        if (k != i) {
            int tmp = a[i];
            a[i] = a[k];
            a[k] = tmp;
        }
    }
}

堆排序

堆排序是利用堆（完全二叉树）这种数据结构而设计的一种排序算法，堆排序是一种选择排序

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
void Sift(int a[], int i, int h) {
    int x = a[i-1];
    int j = 2 * i;
    while (j <= h) {
        if (j < h && a[j-1] < a[j-1+1]) {
            ++j;
        }
        if (x >= a[j-1]) {
            break;
        }
        a[i-1] = a[j-1];
        i = j;
        j = 2 * i;
    }
    a[i-1] = x;
}

void HeapSort(int a[], int n) {
    /*
    构建大顶堆
    从正中间那个结点开始，找到其子结点的较大者交换
    子结点，找到其子结点的子结点的较大者交换
    */
    for (int i = n/2; i > 0; --i) {
        Sift(a, i, n);
    }
    /*
    将堆的根结点与最后一个结点交换，重新构建大顶堆
    将堆的根结点与倒数第二个结点交换 ...
    ...
    */
    for (int i = n; i > 1; --i) {
        int tmp = a[0];
        a[0] = a[i-1];
        a[i-1] = tmp;
        Sift(a, 1, i-1);
    }
}

快速排序

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
/*
选择第一个元素做为基数
从第j个元素开始向前找到一个比基数小的元素赋值到第i个元素，并让i向后移动一个;从第i个元素开始向右找到一个比基数大的元素赋值到第j个元素，并让j向前移动一个;直到i与j值相等，将基数的数据存储第i个元素
*/
int Partition(int a[], int i, int j) {
    int x = a[i];
    while (i < j) {
        while (i < j && a[j] >= x) --j;
        if (i < j) {
            a[i++] = a[j];
        }
        while (i < j && a[i] <= x) ++i;
        if (i < j) {
            a[j--] = a[i];
        }
    }
    a[i] = x;
    return i;
}

void QuickSort(int a[], int low, int high) {
    int p = 0;
    if (low < high) {
        p = Partition(a, low, high); // 选择基数并获取最终的索引
        QuickSort(a, low, p-1); // 快速排序基数之前的数据
        QuickSort(a, p+1, high); // 快速排序基数之后的数据
    }
}

归并排序

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
void outerMerge(int data1[ ], size_t size1, 
				 int data2[ ], size_t size2, int data3[ ]) { //合并有序数组
	int i = 0, j = 0, k = 0;
	for (;k < size1 + size2; k++) {
		if (i < size1 && j < size2) { //需要选择一个放入(比较)
			if (data1[i] < data2[j]) data3[k] = data1[i++];
			else data3[k] = data2[j++];
		} else { //只能从一个数据源放入
			if (i < size1) data3[k] = data1[i++];
			else if (j < size2) data3[k] = data2[j++];
		}
	}
}

void innerMerge(int data[ ], size_t left, 
				 size_t mid, size_t right) { //数组由２个有序子数组
	size_t size = (right - left + 1) * sizeof(data[0]);
	int* temp = (int*)malloc(size);
	outerMerge(data + left, mid - left + 1, data + mid + 1, right - mid, temp);
	memcpy(data + left, temp, size);
	free(temp);
	temp = NULL;
}

void mergeSort(int data[ ], size_t left, size_t right) {//归并排序
	if (left < right) {
		int mid = (left + right) / 2;
		mergeSort(data, left, mid);//排序mid之前
		mergeSort(data, mid + 1, right);//排序mid之后
		innerMerge(data, left, mid, right);
	}
}

总结：

  1. 时间复杂度
    1) 直接插入、直接选择、冒泡排序算法的时间复杂度O($n^2$)
    2) 快速、归并、堆排序算法的时间复杂度为O($nlog_2n$)
    3) 希尔排序算法的时间复杂度很难计算，有几种较接近的答案：O($nlog_2n$)或O($n^{1.25}$)
  2. 稳定性
    1) 直接插入、冒泡、归并排序算法是稳定的
    2) 直接选择、希尔、快速和堆排序算法是不稳定的
  3. 空间复杂度
    1) 直接插入、直接选择、冒泡、希尔和堆排序算法空间复杂度为O(1)
    2) 快速排序算法空间复杂度为O($log_2n$)
    3) 归并排序算法空间复杂度为O($n$)
  4. 排序算法的选取
    1) 若待排序的一组记录数目n较小（如$n \leq 50$）时，可采用插入排序或选择排序
    2) 若$n$较大时，则就采用快速排序、堆排序或归并排序
    3) 若待排序记录按关键字基本有序时，则适宜用直接插入排序或冒泡排序
    4) 关键字比较次数与记录的初始排列顺序无关的排序方法是选择排序
-------------本文结束感谢您的阅读-------------