排序算法总结
山东大学刘鹏昊
-
选择排序
-
思想
找出最大的元素移动到最后 然后找出次大的元素移动到倒数第二位 依次进行 -
算法代码
int* select_sort(int *s,int n){ int tmp_pos; for (int i = n-1; i >= 1; --i) { tmp_pos = i; for (int j = 0; j < i; ++j) { if (s[j]>s[tmp_pos]) tmp_pos = j; } if (tmp_pos!=i){ swap(s[i],s[tmp_pos]); } } }
-
稳定性
不稳定 -
复杂度
O(n2)
-
- 冒泡排序
-
思想
从最低位开始相邻元素相互比较交换位置 每次都能保证最大元素移动到最右边 n-1次后完成 -
算法代码
int* bubble_sort(int *s,int n){ for (int i = n-1; i >=1 ; --i) { for (int j = 0; j < i; ++j) { if (s[j]>s[j+1]){ swap(s[j],s[j+1]); } } } }
-
稳定性
稳定 -
复杂度
O(n2)
-
- 插入排序
-
思想
从最低位开始相邻元素相互比较交换位置 每次都能保证最大元素移动到最右边 n-1次后完成 -
算法代码
int* insertion_sort(int *s,int n) { for (int i = 1; i < n; i++) { if (s[i - 1] > s[i]) { int temp = s[i]; int j = i; while (j > 0 && s[j - 1] > temp) { s[j] = s[j - 1]; j--; } s[j] = temp; } } return s; }
-
稳定性
稳定 -
复杂度
O(n2)
-
- 快速排序
-
思想
将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小 然后递归分别快速排序这两部分 -
算法代码
void quick_sort(int a[], int low, int high) { if(low >= high) { return; } int first = low; int last = high; int key = a[first]; while(first < last) { while(first < last && a[last] >= key) { --last; } a[first] = a[last]; while(first < last && a[first] <= key) { ++first; } a[last] = a[first]; } a[first] = key; quick_sort(a, low, first-1); quick_sort(a, first+1, high); }
-
稳定性
不稳定 -
复杂度
O(nlog(n))
-
- 箱子排序
-
思想
将每个元素抽象为关键字(可排序的) 然后遍历依次放入相应关键字的箱子中 然后顺序输出 就是有序的 -
算法代码
Node_list<T> *bin = new Node_list<T>[range]; T maximum = data[0]; for (int i = 0; i < length; ++i) { if (data[i] > maximum) { maximum = data[i]; } } int loop_value = range; do { for (int i = 0; i < length; ++i) { bin[data[i] % loop_value / (loop_value / range)].push(data[i]); } int index_in_bin = 0; for (int i = 0; i < length; ++i) { while (bin[index_in_bin].length == 0) { index_in_bin++; } data[i] = bin[index_in_bin].shift(); } loop_value *= range; cout << "step : "; output(); } while (loop_value / range <= maximum);
-
稳定性
不稳定 -
复杂度
O(n)
-