面向实习面试的复习之排序

发表于

最近一直在寻找暑假的实习，照道理来说排序应该是一个高频的面试问题，不过至今也只遇到了描述一下快速排序思想的问题，这里参考了大二算法课上老师所讲的算法以及《算法》（第4版）的内容，使用C++做了练习。
如果有错误的话，也欢迎告诉我。（不过博客还没有评价系统..）

冒泡

时间复杂度 O(n2)


1
2
3
4
5
6
void bubble_sort(vector<int> &numbers) {
    for (int i = 0; i < numbers.size(); i++) 
        for (int j = i + 1; j < numbers.size(); j++) 
            if (numbers[i] < numbers[j]) 
                swap(number[i], numbers[j]);
}


选择

时间复杂度 O(n2)


1
2
3
4
5
6
7
8
void choose_sort(vector<int> &numbers) {
	for (int i = 0; i < numbers.size(); i++) {
		int min = i;
		for (int j = i + 1; j < numbers.size(); j++) 
	    	if (numbers[min] > numbers[j]) min = j;       
	    swap(numbers[i], numbers[min]);
	}
}


插入

时间复杂度 O(n2)


1
2
3
4
5
6
void insert_sort(vector<int> &numbers) {
	for (int i = 1; i < numbers.size(); i++) {
		for (int j = i; j > 0 && numbers[j] < numbers[j - 1]; j--)
	    	swap(numbers[j], numbers[j - 1]);
	}
}


快排

时间复杂度O(nlogn) 最坏状态 O(n2)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int partition(vector<int> &numbers, int lo, int hi) {
	int i = lo; int j = hi + 1;
	int n = numbers[lo];
	while (true) {
		while (numbers[++i] < n) if (i == hi) break;        
		while (numbers[--j] > n) if (j == lo) break;
        if (i >= j) break;
        swap(numbers[i], numbers[j]);
    }
    swap(numbers[lo], numbers[j]);
    return j;
}
void quick_sort(vector<int> &numbers, int lo, int hi) {
    if (lo >= hi) return;
    int j = partition(numbers, lo, hi);
    quick_sort(numbers, lo, j - 1);
    quick_sort(numbers, j + 1, hi);
}

归并

时间复杂度O(nlogn)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int merge(vector<int> &numbers, int lo, int mid, int hi) {
    int i = lo; int j = mid + 1;
    vector<int> copy;
    copy = numbers;
    for (int k = lo; k <= hi; k++) {
        if (i > mid) numbers[k] = copy[j++];
        else if (j > hi) numbers[k] = copy[i++];
        else if (copy[i] < copy[j]) numbers[k] = copy[j++];
        else numbers[k] = copy[i++];
    }
}
void merge_sort(vector<int> &numbers, int lo, int hi) {
    if (lo >= hi) return;
    int mid = lo + (hi - lo) / 2;
    merge_sort(numbers, lo, mid);
    merge_sort(numbers, mid + 1, hi);
    merge(numbers, lo, mid, hi);
}