Martin

爱设计，爱创造|To design and create

高效排序算法汇总

直接插入排序（insert sort）

它的基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增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
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
#include <stdio.h>
#include <time.h>
#define MAX_ELEMENT 20000

// 原理
void insertSort(int v[], int n)
{
	int i,j,k;
	for (i = 1; i < n; ++i)
	{
	    // 假设i前面的（0...i-1）已经有序，如果v[i]<v[i-1],则需为v[i]进行排序
		if(v[i] < v[i-1])
		{
			for (j = 0; j < i; ++j)
			{
			    // 寻找插入位置
				if (v[i] < v[j])
				{
					int temp = v[i];
					// 移后
					for (k = i-1; k > j-1; --k)
					{
						v[k+1] = v[k];
					}
					// 插入
					v[j] = temp;
					break;
				}
			}
		}
	}
}

void insertSort1(int v[], int n)
{
	int i,j;
	for (i = 1; i < n; ++i)
	{
		if (v[i] < v[i-1])
		{
			int temp = v[i];
			// 边找位置边移后
			for (j = i-1; j >= 0 && v[j] > temp; --j)
			{
				v[j+1] = v[j];
			}
			v[j+1] = temp;
		}
	}
}

// 最简版
void insertSort2(int v[], int n)
{
	int i,j,temp;
	for (int i = 1; i < n; ++i)
	{
		for (int j=i-1; j >=0 && v[j] > v[j+1]; --j)
		{
			temp = v[j];
			v[j] = v[j+1];
			v[j+1] = temp;
		}
	}
}

// test
main()
{
	int test[MAX_ELEMENT];
	for (int i = 0; i < MAX_ELEMENT; ++i)
	{
		test[i] = MAX_ELEMENT-i-1;
	}
	clock_t time_taken;
	insertSort2(test, MAX_ELEMENT);
	printf("%d\n", test[2555]);//2555
	time_taken = clock() - time_taken;
	printf("took %lu clocks (%lu seconds)\n",
           (unsigned long) time_taken,
           (unsigned long) time_taken / CLOCKS_PER_SEC);
}

Reference

希尔排序(shell sort)

希尔排序的实质就是分组插入排序，该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。

该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void shellSort(int *arr, int n) {
	int temp;
	int step = n;
	int i,j;
	//增量序列为n/2,n/4,...,1
	while((step /= 2)) {
	    //做增量为step的直接插入排序
		for (i = step+1; i < n; ++i)
		{
			for (j = i-step; j>=0 && arr[j]>arr[j+step]; j-=step)
			{
				temp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = temp;
			}
		}
	}
}

起泡(bubble sort)排序

起泡排序是非常容易理解和实现，，以从小到大排序举例：

设数组长度为N。

  1. 比较相邻的前后二个数据，如果前面数据大于后面的数据，就将二个数据交换。

  2. 这样对数组的第0个数据到N-1个数据进行一次遍历后，最大的一个数据就“沉”到数组第N-1个位置。

  3. N=N-1，如果N不为0就重复前面二步，否则排序完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void bubbleSort(int *arr, int n) {
	int temp;
	int flag;
	int i, j;
	for (i = n; i > 1; --i)
	{
	    flag = 0;
		for (j = 1; j < i; ++j)
		{
			if(arr[j-1] > arr[j]) {
				temp = arr[j-1];
				arr[j-1] = arr[j];
				arr[j] = temp;
				flag=1;
			}
		}
		//当某一趟不交换时则有序
		if(flag == 0) return;
	}
}

快速排序

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。

该方法的基本思想是：

  1. 先从数列中取出一个数作为基准数。

  2. 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

  3. 再对左右区间重复第二步，直到各区间只有一个数。

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
void quickSort(int *arr, int l, int r) {
    if(l >= r) return;
    int i = l;
    int j = r;
    //挖坑
    int x = arr[l];
    while(i<j) {
        //从最右边找数
        while(i<j && x <= arr[j]) {
            --j;
        }
        //填坑
        if(i<j) arr[i++]=arr[j];
        //从最左边找数
        while(i<j && x > arr[i]) {
            ++i;
        }
        //再填坑
        if(i<j) arr[j--]=arr[i];
    }
    //直到i=j时,小于x的在i的左边，大于x的在i的右边
    arr[i] = x;
    //分治法
    quickSort(arr, l, i-1);
    quickSort(arr, i+1, r);
}

直接选择排序

直接选择排序和直接插入排序类似，都将数据分为有序区和无序区，所不同的是直接播放排序是将无序区的第一个元素直接插入到有序区以形成一个更大的有序区，而直接选择排序是从无序区选一个最小的元素直接放到有序区的最后。

设数组为a[0…n-1]。

  1. 初始时，数组全为无序区为a[0..n-1]。令i=0

  2. 在无序区a[i…n-1]中选取一个最小的元素，将其与a[i]交换。交换之后a[0…i]就形成了一个有序区。

  3. i++并重复第二步直到i==n-1。排序完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void selectSort(int *arr, int n) {
	int temp;
	for (int i = 0; i < n; ++i)
	{
		for (int j = i; j < n; ++j)
		{
			if(arr[j] < arr[i]) {
				temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
			}
		}
	}
}

堆排序

Reference

二叉堆的定义
二叉堆是完全二叉树或者是近似完全二叉树。

二叉堆满足二个特性：

  1. 父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值。

  2. 每个结点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）。

当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆。

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
//插入一个位置为i结点的结点后，对arr进行堆化
void minHeapFixUp(int *arr, int i) {
	//i的父结点位置
	int j = (i-1)/2;
	int temp = arr[i];
	while(j>=0 && i!=0) {
		if(arr[j]<=temp) break;
		//将较大的子结点往下移动，替换它的子结点
		arr[i] = arr[j];
		i = j;
		j = (i-1)/2;
	}
	arr[i] = temp;
}

//插入操作
void minHeapAddNum(int *arr, int n, int num) {
	arr[n] = num;
	minHeapFixUp(arr, n);
}

//删除第一个元素arr[0]后对arr进行堆化
void minHeapFixDown(int *arr, int i, int n) {
	//i的子结点位置:i*2+1或者i*2+2
	int j = i*2+1;
	int temp = arr[i];
	while(j<n) {
		//取两子中最小
		if(j+1<n && arr[j+1]<arr[j]) ++j;
		if(arr[j]>=temp) break;
		arr[i] = arr[j];
		i=j;
		j = i*2+1;
	}
	arr[i] = temp;
}

//删除操作(删除第一个结点，然后用最后一个结点替换)
void minHeapDel(int *arr, int n) {
	int temp = arr[n-1];
	arr[n-1] = arr[0];
	arr[0] = temp;
	minHeapFixDown(arr, 0, n-1);
}

//建立最小堆
void makeMinHeap(int *arr, int n) {
	if(n<=1) return;
	for (int i = n/2-1; i >= 0; --i)
	{
		minHeapFixDown(arr, i, n);
	}
}

//最小堆排序，即生成递减数组
void minHeapSort(int *arr, int n) {
	makeMinHeap(arr, n);
	int temp;
	for (int i = n-1; i >= 1; --i)
	{
		temp = arr[0];
		arr[0] = arr[i];
		arr[i] = temp;
		minHeapFixDown(arr, 0, i);
	}
}

归并(merge)排序

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
//将有二个有序数列a[first...mid]和a[mid...last]合并。  
void mergearray(int a[], int first, int mid, int last, int temp[])  
{  
    int i = first, j = mid + 1;  
    int m = mid,   n = last;  
    int k = 0;  
      
    while (i <= m && j <= n)  
    {  
        if (a[i] <= a[j])  
            temp[k++] = a[i++];  
        else  
            temp[k++] = a[j++];  
    }  
      
    while (i <= m)  
        temp[k++] = a[i++];  
      
    while (j <= n)  
        temp[k++] = a[j++];  
      
    for (i = 0; i < k; i++)  
        a[first + i] = temp[i];  
} 

void mergeSort1(int *arr, int first, int last, int *temp) {
    if(first < last) {
        int mid = (first + last)/2;
        //分治法
        mergeSort1(arr,first,mid,temp);
        mergeSort1(arr,mid+1,last,temp);
        //前后两部分有序序列合并
        mergearray(arr,first,mid,last,temp);
    }
}

void mergeSort(int *arr, int n) {
    int *p;
    if(!(p=(int*)malloc(n*sizeof(int))))
        exit(-1);
    mergeSort1(arr, 0, n-1, p);
    free(p);
}
技术 算法

Proudly powered by Hexo and Theme by Hacker
© 2021 Martin Yong