八大排序算法
image.png
算法分析
1. 直接插入排序：
在遍历数组元素的时候，当前元素 array[i] 从当前位置从右向左查找，直到找到正确的位置，使得该元素插入后能够得到从 0 到 i 有序的数组；
image.png
如图：
- i = 1 时，当前元素 3 和 它前面(下标 j = i - 1 到 j = 0)的元素比较，因为 9 > 3 ，所以 9 右移一位（array[j + 1] = array[j]）； j 到头了，所以将 3 插入到位置 (j = 0)；此时，array = [3, 9, 0, 7, 2, 1]；
- i = 2 时，当前元素 0 和 它前面(下标 j = i - 1 到 j = 0)的元素比较，因为 9 > 0 ，所以 9 右移一位（array[j + 1] = array[j]）；因为 3 > 0 ，所以 3 右移一位（array[j + 1] = array[j]）， j 到头了，所以将 0 插入到位置 (j = 0)；此时，array = [0, 3, 9, 7, 2, 1]；
- i = 3 时，当前元素 7 和 它前面(下标 j = i - 1 到 j = 0)的元素比较，因为 9 > 7 ，所以 9 右移一位（array[j + 1] = array[j]）；因为 3 < 7 ，所以将 7 插入 3 的右面，即位置(j + 1 = 2)；此时，array = [0, 3, 7, 9, 2, 1]；
重复上述插入过程，直到数组的最后一个元素插入结束，排序完成。
程序设计
class solution {
public:
void insert_sort(vector<int> &array) { // 直接插入排序
int index;
for (int i = 1; i < array.size(); i++) {
int temp = array[i];
for (int j = i - 1; j >= 0; j--) {
if(temp < array[j]){
array[j + 1] = array[j];
index = j;
}
else {
index = j + 1;
break;
}
}
array[index] = temp;
}
}
好了，接下来我们分析下直接插入排序的时间复杂度：
首先分析直接插入排序时间复杂度的最好情况：
其实从程序上就不难看出，让程序中的for (int j = i - 1; j >= 0; j--) 循环始终走 else 的条件分支就行了，令数组初始时就是小到大递增的有序数组(1, 2, 3, 4, 5)或者数组中所有元素都相等(6, 6, 6, 6, 6)，此时的时间复杂度为O（n）;
最坏的情况就是每次当前元素的插入位置都是数组头元素，令数组初始时就是从大到小递减的有序数组(5, 4, 3, 2, 1)，此时的时间复杂度为O（n²）。
2. 希尔排序：
to be continue
#include <iostream>
#include <vector>
using namespace std;
class solution {
public:
void insert_sort(vector<int> &array) { // 直接插入排序
int index;
for (int i = 1; i < array.size(); i++) {
int temp = array[i];
for (int j = i - 1; j >= 0; j--) {
if(temp < array[j]){
array[j + 1] = array[j];
index = j;
}
else {
index = j + 1;
break;
}
}
array[index] = temp;
//for (int i = 0; i < array.size(); i++) {
// cout << array[i] << ' ';
//}
//cout << endl;
}
}
void shell_sort(vector<int> &array) { // 希尔（shell）排序
int step = array.size() / 2;
int index;
while (step != 0) {
for (int i = step; i < array.size(); i++) {
int temp = array[i];
for (int j = i - step; j >= 0; j -= step) {
if (temp < array[j]) {
array[j + step] = array[j];
index = j;
}
else {
index = j + step;
break;
}
}
array[index] = temp;
}
step = step / 2;
//for (int i = 0; i < array.size(); i++) {
// cout << array[i] << ' ';
//}
//cout << endl;
}
}
void select_sort(vector<int> &array) { // 简单选择排序
int min_array;
int index;
for (int i = 0; i < array.size(); i++) {
min_array = array[i];
index = i;
for (int j = i + 1; j < array.size(); j++) {
if (array[i] > array[j]) {
min_array = array[j];
index = j;
}
}
array[index] = array[i];
array[i] = min_array;
//for (int i = 0; i < array.size(); i++) {
// cout << array[i] << ' ';
//}
//cout << endl;
}
}
void heap_sort(vector<int> &array) { // 堆排序
int len = array.size();
int index = len / 2 - 1;
for (int i = index; i >= 0; i--) {
creat_heap(array, i, len);
}
for (int i = len - 1; i >= 1; i--) {
swap(array[0], array[i]);
creat_heap(array, 0, i);
}
}
void quick_sort(vector<int> &array, int left, int right) { // 快速排序
if (left < right) {
int i = left;
int j = right;
int pivot = array[i];
while (i < j) {
while (i < j && array[j] >= pivot) {
j -= 1;
}
if (i < j) {
array[i] = array[j];
i += 1;
}
while (i < j && array[i] <= pivot) {
i += 1;
}
if (i < j) {
array[j] = array[i];
j -= 1;
}
}
array[i] = pivot;
//for (int i = 0; i < array.size(); i++) {
// cout << array[i] << ' ';
//}
//cout << endl;
quick_sort(array, left, i - 1);
quick_sort(array, i + 1, right);
}
}
void bubble(vector<int> &array) { // 冒泡排序
for (int i = 1; i < array.size(); i++) {
for (int j = 0; j < array.size() - i; j++) {
if (array[j] > array[j + 1]) {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
//for (int i = 0; i < array.size(); i++) {
// cout << array[i] << ' ';
//}
//cout << endl;
}
}
void merge_sort(vector<int> &array) { // 归并排序
if (array.size() < 2) {
return;
}
int mid = array.size() / 2;
vector<int> array_1;
vector<int> array_2;
for (int i = 0; i < mid; i++) {
array_1.push_back(array[i]);
}
for (int i = mid; i < array.size(); i++) {
array_2.push_back(array[i]);
}
merge_sort(array_1);
merge_sort(array_2);
array.clear();
merge_two_array(array_1, array_2, array);
//for (int i = 0; i < array.size(); i++) {
// cout << array[i] << ' ';
//}
//cout << endl;
}
private:
void creat_heap(vector<int> &array, int index, int len) { //堆排序构建堆
int left = 2 * index + 1;
int right = 2 * index + 2;
int max_node_index = index;
if (left < len && array[max_node_index] < array[left]) {
max_node_index = left;
}
if (right < len && array[max_node_index] < array[right]) {
max_node_index = right;
}
if (max_node_index != index) {
swap(array[index], array[max_node_index]);
creat_heap(array, max_node_index, len);
}
//for (int i = 0; i < array.size(); i++) {
// cout << array[i] << ' ';
//}
//cout << endl;
}
void merge_two_array(vector<int> &array_1, vector<int> &array_2, vector<int> &array) { // 归并排序合并
int i = 0;
int j = 0;
while (i < array_1.size() && j < array_2.size()) {
if (array_1[i] < array_2[j]) {
array.push_back(array_1[i]);
i += 1;
}
else {
array.push_back(array_2[j]);
j += 1;
}
}
while (i < array_1.size()) {
array.push_back(array_1[i]);
i += 1;
}
while (j < array_2.size()) {
array.push_back(array_2[j]);
j += 1;
}
}
};
int main() {
int n;
while (cin >> n && n != 0) {
vector<int> array(n);
for (int i = 0; i < n; i++) {
cin >> array[i];
}
solution s;
//s.insert_sort(array);
//s.shell_sort(array);
//s.select_sort(array);
s.heap_sort(array);
//s.quick_sort(array, 0, n - 1);
//s.bubble(array);
//s.merge_sort(array);
for (int i = 0; i < array.size(); i++) {
cout << array[i] << ' ';
}
cout << endl;
}
system("pause");
return 0;
}
