八大排序算法
image.png
算法分析
1. 直接插入排序：
在遍歷數(shù)組元素的時(shí)候般堆，當(dāng)前元素 array[i] 從當(dāng)前位置從右向左查找在孝，直到找到正確的位置，使得該元素插入后能夠得到從 0 到 i 有序的數(shù)組淮摔；
image.png
如圖：
- i = 1 時(shí)私沮，當(dāng)前元素 3 和 它前面(下標(biāo) j = i - 1 到 j = 0)的元素比較，因?yàn)?9 > 3 ，所以 9 右移一位（array[j + 1] = array[j]）仔燕； j 到頭了造垛，所以將 3 插入到位置 (j = 0)；此時(shí)晰搀，array = [3, 9, 0, 7, 2, 1]五辽；
- i = 2 時(shí)，當(dāng)前元素 0 和 它前面(下標(biāo) j = i - 1 到 j = 0)的元素比較外恕，因?yàn)?9 > 0 杆逗，所以 9 右移一位（array[j + 1] = array[j]）；因?yàn)?3 > 0 鳞疲，所以 3 右移一位（array[j + 1] = array[j]）罪郊， j 到頭了，所以將 0 插入到位置 (j = 0)尚洽；此時(shí)悔橄，array = [0, 3, 9, 7, 2, 1]；
- i = 3 時(shí)腺毫，當(dāng)前元素 7 和 它前面(下標(biāo) j = i - 1 到 j = 0)的元素比較癣疟，因?yàn)?9 > 7 ，所以 9 右移一位（array[j + 1] = array[j]）潮酒；因?yàn)?3 < 7 睛挚，所以將 7 插入 3 的右面，即位置(j + 1 = 2)急黎；此時(shí)竞川，array = [0, 3, 7, 9, 2, 1]；
重復(fù)上述插入過程叁熔，直到數(shù)組的最后一個(gè)元素插入結(jié)束，排序完成床牧。
程序設(shè)計(jì)
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;
}
}
好了荣回，接下來我們分析下直接插入排序的時(shí)間復(fù)雜度：
首先分析直接插入排序時(shí)間復(fù)雜度的最好情況：
其實(shí)從程序上就不難看出，讓程序中的for (int j = i - 1; j >= 0; j--) 循環(huán)始終走 else 的條件分支就行了戈咳，令數(shù)組初始時(shí)就是小到大遞增的有序數(shù)組(1, 2, 3, 4, 5)或者數(shù)組中所有元素都相等(6, 6, 6, 6, 6)心软，此時(shí)的時(shí)間復(fù)雜度為O（n）;
最壞的情況就是每次當(dāng)前元素的插入位置都是數(shù)組頭元素，令數(shù)組初始時(shí)就是從大到小遞減的有序數(shù)組(5, 4, 3, 2, 1)著蛙，此時(shí)的時(shí)間復(fù)雜度為O（n2）删铃。
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) { // 簡(jiǎn)單選擇排序
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) { //堆排序構(gòu)建堆
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;
}
