0x01 排序
1. 选择排序
首先取出第一个值，其位置记做k，然后遍历找到比k位置的值小的值，把比k位置小的值的位置赋值给k，直到第一轮遍历结束，然后交换第一个位置与k位置的值。再取出第二个值，以此类推。
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
42void printNum(int array[], int length) {
for (int i = 0; i < length; i++) {
NSLog(@"数字：%d", array[i]);
}
}
void swap(int array[], int i, int j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
void selectionSort(int array[], int length) {
int k = -1;
for (int i = 0; i < length; i++) {
k = i;
for (int j = i+1; j < length; j++) {
if(array[j] < array[k]) {
k = j;
}
}
if(i != k) swap(array, i, k);
}
}
- (void)viewDidLoad {
[super viewDidLoad];
int array[] = {21, 31, 6, 19, 87, 54, 18};
int length = sizeof(array) / sizeof(*array);
selectionSort(array, length);
printNum(array, length);
}
// 运行结果：
2018-04-25 10:17:16.803588+0800 testData[69629:150010320] 数字：6
2018-04-25 10:17:16.803741+0800 testData[69629:150010320] 数字：18
2018-04-25 10:17:16.803833+0800 testData[69629:150010320] 数字：19
2018-04-25 10:17:16.803935+0800 testData[69629:150010320] 数字：21
2018-04-25 10:17:16.804042+0800 testData[69629:150010320] 数字：31
2018-04-25 10:17:16.804150+0800 testData[69629:150010320] 数字：54
2018-04-25 10:17:16.804249+0800 testData[69629:150010320] 数字：87
2. 插入排序
假设在序号i（i>=1）之前的元素即[0..i-1]都已经排好序，本趟需要找到i对应的元素x的正确位置k，并且在寻找这个位置k的过程中逐个将比较过的元素往后移一位，为元素x“腾位置”，最后将k对应的元素值赋为x。
1
2
3
4
5
6
7
8
9
10
11
12
13
14void InsertionSort(int array[], int length) {
int k = -1;
for (int i = 1; i < length; i++) {
k = i;
int temp = array[k];
for (int j = i - 1; j >= 0; j--) {
if (array[j] > temp) {
array[j+1] = array[j];
k = j;
}
}
array[k] = temp;
}
}
3. 冒泡排序
从最后开始两两对比，小的话交换位置。
1
2
3
4
5
6
7
8
9void BubbleSort(int array[], int length) {
for (int i = 0; i < length; i++) {
for (int j = length - 1; j > i; j--) {
if(array[j] < array[j-1]) {
swap(array, j, j-1);
}
}
}
}
4. 希尔排序
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
这个是不稳定的一种排序方法，时间复杂度O(n*logn)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18void ShellSort(int array[], int length) {
int gap = length;
int k = -1;
do {
gap = gap / 3 + 1;
for (int i = gap; i < length; i++) {
k = i;
int temp = array[k];
for (int j = i - gap; j >= 0; j -= gap) {
if(temp < array[j]) {
array[i] = array[j];
k = j;
}
}
array[k] = temp;
}
}while (gap > 1);
}
5. 快速排序
任取待排序序列中的某个数据元素(例如:第一个元素)作为基准，左边都是比基准数小的元素，右边都是比基准数大的元素。再对左右的序列进行同样的操作，直到排序正确。
这个是不稳定的一种排序方法，时间复杂度O(n*logn)。
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
28int cut(int array[], int low, int high) {
if(low > high) return -1;
int pv = array[low];
while (low < high) {
while (low < high && array[high] >=pv) {
high--;
}
swap(array, low, high);
while (low < high && array[low] <= pv) {
low++;
}
swap(array, low, high);
}
return low;
}
void QSort(int array[], int low, int high) {
if(low >= high) return;
int p = cut(array, low, high);
QSort(array, low, p - 1);
QSort(array, p + 1, high);
}
void QuickSort(int array[], int length) {
QSort(array, 0, length - 1);
}
6. 归并排序
将两个位置相邻的记录有序子序列归并为一个记录有序的序列。
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
41void Merge(int src[], int des[], int low, int mid, int high) {
// mid+1为第2有序区第1个元素，mid为第1有序区的最后1个元素
int i = low; // i指向第1有序区的第1个元素
int j = mid + 1; // j指向第2有序区的第1个元素，high为第2有序区的最后一个元素
int k = low;
while (i <= mid && j <= high) {
if (src[i] < src[j]) {
des[k++] = src[i++];
}else{
des[k++] = src[j++];
}
}
// 比完之后，假如第1个有序区仍有剩余，则直接全部复制到temp数组
while (i <= mid) {
des[k++] = src[i++];
}
// 比完之后，假如第2个有序区还有剩余，则直接全部复制到temp数组
while (j <= high) {
des[k++] = src[j++];
}
}
void MSort(int src[], int des[], int low, int high, int max) {
if (low == high) {
des[low] = src[low];
}else{
int mid = (low + high) / 2;
int *space = (int *)malloc(sizeof(int) * max);
if(space != NULL) {
MSort(src, space, low, mid, max);
MSort(src, space, mid+1, high, max);
Merge(space, des, low, mid, high);
}
free(space);
}
}
void MergeSort(int array[], int length) {
MSort(array, array, 0, length - 1, length);
}
0x02 查找
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// 递归实现
// 返回数组下标,key为要查找的值
int Binary_Search_R(int array[], int low, int high, int key) {
if(low > high) return -1;
int index = -1;
int mid = (low + high) / 2;
if(array[mid] == key) {
index = mid;
}else if (array[mid] < key) {
index = Binary_Search_R(array, mid+1, high, key);
}else if (array[mid] > key) {
index = Binary_Search_R(array, low, mid-1, key);
}
return index;
}
// 非递归实现
int Binary_Search(int array[], int low, int high, int key) {
if(low > high) return -1;
int index = -1;
while (low <= high) {
int mid = (low + high) / 2;
if (array[mid] == key) {
index = mid;
break;
}else if (array[mid] < key) {
low = mid+1;
}else if (array[mid] > key) {
high = mid-1;
}
}
return index;
}
但是这样的查找，如果查找的数是第一位，那么显然在1/4处开始查找要比1/2处开始查找效率要高，所以我们需要算出一个动态的中间值，而不是一味的(low + high) / 2这样算中间值。对于(low + high) / 2，等价于low + (high - low) / 2。我们可以设1/2为f(x)，得出mid = low + f(x) * (high - low)，f(x) = (mid - low) / (high - low)。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21int Interpolation_Search(int array[], int low, int high, int key) {
if(low > high) return -1;
int index = -1;
while (low <= high) {
float fx = 1.0f * (key - array[low]) / (array[high] - array[low]);
int mid = low + fx * (high - low);
if (array[mid] == key) {
index = mid;
break;
}else if (array[mid] < key) {
low = mid+1;
}else if (array[mid] > key) {
high = mid-1;
}
}
return index;
}
二分查找由于是基于有序的线性表，所以效率为O(logn)。