该篇博客介绍的经典算法有：冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序

冒泡排序 Bubble Sort

概念：依次比较相邻两个元素的大小，这样一轮比较下来就可以得出当前轮的最值。

步骤：

1、比较相邻的两个元素

2、若左侧元素值较大，则交换位置

3、第i轮比较范围为[0,n-i]，得到第i大元素

4、到没有交换时即说明排序完成

代码：

1
2
3
4
5
6
7
8
9
10
void bubble_sort(int a[], int n) {
    for(int i=0; i<n; ++i) {
    	for(int j=1; j<n-i; ++j) {
    		if(a[j] < a[j-1]) {
    			swap(a[j], a[j-1]);
    		}
    	}
    }
    return;
}

复杂度：

  • 最差时间复杂度：O(n^2)

  • 最佳时间复杂度：O(n)[需在原代码基础上加标志位优化，见下文]

  • 平均时间复杂度：O(n^2)

优化：

1、添加标志位，当序列有序时，停止冒泡；时间复杂度提升至O(n)

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
void cocktail_sort(int arr[], int len) {
    int left = 0;
    int right = len-1;
    bool swapped = true;//标志是否已经还需要排序
    while(swapped) {
        swapped = false;
    	for(i=left; i<right; ++i) {
    		if(arr[i] > arr[i+1]) {
    			swap(arr[i], arr[i+1]);
    			swapped = true;
    		}
    	}
    	
    	--right;
    	
    	for(i=right; i>left; --i) {
    		if(arr[i] < arr[i-1]) {
    			swap(arr[i], arr[i-1]);
    			swapped = true;
    		}
    	}
    	
    	++left;
    }
    return;
}

选择排序

概念：每次从未排序部分中找出最小值，放在已排序部分后面。

步骤：

1、在未排序部分找出最小值，放在已排序部分后面

2、重复1的操作直到全部排好序

源代码：

1
2
3
4
5
6
7
8
9
10
void select_sort(int a[], int n) {
    for(int i=0; i<n; ++i) {
        int min = i;
        for(int j=i+1; j<n; ++j) {
            if(a[min] > a[j])
                min = j;
        }
        swap(a[i], a[min]);
    }
}

复杂度：

  • 最差时间复杂度：O(n^2)

  • 最佳时间复杂度：O(n^2)

  • 平均时间复杂度：O(n^2)

插入排序

概念：对于每个未排序数据，扫描已排序数组，并插入到合适的位置。

步骤：

1、第一个元素认为已排序

2、之后每取出一个元素，插入到已排序数组的合适位置

源代码：

1
2
3
4
5
6
7
8
9
10
void insert_sort(int a[], int n) {
    int j;
	for(int i=1; i<n; ++i) {//待排序部分
	    int tmp = a[i];
	    for(j=i-1; j>=0&&a[j]>tmp; --j) {//已排序部分
	        a[j+1] = a[j];
	    }
	    a[j+1] = tmp;
	}
}

复杂度：

最差时间复杂度：O(n^2)

最佳时间复杂度：O(n)

平均时间复杂度：O(n^2)

优化：

1、如果数组范围较大，可采用二分查找，找到第一个比a[i]大的位置再insert即可

希尔排序

概念：是对插入排序的高效改进，将序列每次按不同步长划分，再对每列进行插入排序，是非稳定算法

步骤：每次按不同的步长对数组进行划分行，再对每列进行插入排序，改变步长重复上面的操作，直到步长为1，即得到完全有序的数组

源代码：

1
2
3
4
5
6
7
8
9
10
11
12
void shell_sort(int a[], int n) {
    int j;
    for(int gap = n>>1; gap > 0; gap >>= 1) {
        for(int i=gap; i<n; ++i) {//未排序部分
            int tmp = a[i];
            for(j = i-gap; j>0&&a[j]>tmp; j-=gap) {//已排序部分
                a[j+gap] = a[j];  
            }
            a[j+gap] = tmp;
        }
    }
}

复杂度：

复杂度取决于步长的选择。

归并排序

概念：采用分治法实现，将数组先分解再合并的过程中做到排序

步骤：将数组递归地分为left、right两部分，当left、right分别有序后再合并left、right即可得到排序后的数组。

源代码：

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
void merge_sort(int arr[], int n) {
    int *a = arr;
    int *b = (int*)malloc(n*sizeof(int*));
    int seg, start;
    for(seg = 1; seg < n; seg += seg) {
        for(start = 0; start < n; start += seg + seg) {
            int low = start;
            int mid = min(start+seg, n);
            int high = min(start+seg+seg, n);
            int start1 = low;
            int end1 = mid;
            int start2 = mid;
            int end2 = high;
            int k = low;
            while(start1 < end1 && start2 < end2) {
                b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
            }
            while(start1 < end1) {
                b[k++] = a[start1++];
            }
            while(start2 < end2) {
                b[k++] = a[start2++];
            }
        }
        int *tmp = a;
        a = b;
        b = tmp;
    }
    if(a != arr) {
        int i;
        for(i = 0; i < n; ++i) {
            b[i] = a[i];
        }
        b = a;
    }
    free(b);
}

复杂度：

最差时间复杂度：O(nlogn)

最佳时间复杂度：O(n)

平均时间复杂度：O(nlogn)

快速排序

概念：每次把序列以基准划分为左右两部分，重新排列使左侧部分小于基准，右侧部分大于基准。再对基准左右两侧分别进行排序。

步骤：

1、挑出一个元素作为基准

2、重新排序，使得比基准小的元素都放在基准左侧，比基准大的元素都放在基准右侧。

3、递归地对基准左右两侧数据进行排序

源代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void quick_sort(int a[], int start, int end) {
	if(start >= end)
		return ;
	int mid = a[end];
	int left = start;
	int right = end - 1;
	while(left < right) {
		while(a[left] < mid && left < right)
			++left;
		while(a[right] >= mid && left < right)
			--right;
		swap(&a[left], &a[right]);
	}
	if(a[left] >= a[end]) {
		swap(&a[left], &a[end]);
	} else ++left;
	quick_sort(a, start, left-1);
	quick_sort(a, left+1, end);
}

复杂度：

最差时间复杂度：O(n^2)

最佳时间复杂度：O(nlogn)

平均时间复杂度：O(nlogn)