排序: 稳定排序算法, 不稳定排序算法
如上图, 若两个 5 排序之后交换了位置就是不稳定的, 没有交换位置就是稳定排序
1. 选择排序
冒泡是相邻的两个交换, 选择法是首元素与最小的交换.
- void xuanzhepaixu(int* my_array, int len)
- {
- for (int i = 0; i <len - 1; ++i) {
- for (int j = i + 1; j < len; ++j) {
- if (my_array[i]> my_array[j]) {// 交换次数多, 不如记录下表位置效率高
- int temp = my_array[i];
- my_array[i] = my_array[j];
- my_array[j] = temp;
- }
- }
- }
- }
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- // 选择法排序
- void xuanzhepaixu(int* my_array, int len)
- {
- int min = 0;
- for (int i = 0; i <len - 1; ++i) {
- min = i;
- for (int j = i + 1; j < len; ++j) {
- if (my_array[min]> my_array[j]) {
- min = j;// 保存最小元素的位置
- }
- }
- if ( min != i ) {
- int temp = my_array[i];
- my_array[i] = my_array[min];
- my_array[min] = temp;
- }
- }
- }
- void my_print_array(int* my_array, int len)
- {
- for (int i = 0; i <len; ++i) {
- printf("]", my_array[i]);
- }
- printf("\n");
- }
- int main()
- {
- int my_array[] = {10, 6, 7, 4, 9, 8, 5, 1, 3, 2};
- int len = sizeof(my_array) / sizeof(int);
- xuanzhepaixu(my_array, len);
- my_print_array(my_array, len);
- system("pause");
- return 0;
- }
2. 冒泡排序
- void maopaopaixu(int* my_array, int len)
- {
- for (int i = 0; i < len; ++i) {
- for (int j = 1; j < len; ++j) {
- if ( my_array[j]> my_array[j - 1] ) {
- int temp = my_array[j];
- my_array[j] = my_array[j - 1];
- my_array[j - 1] = temp;
- }
- }
- }
- }
冒泡算法的优化, 在待排序数据处于一种趋于有序的情况, 可以减少判断次数, 比如: 1,2,3,4,7,5,6
- void maopaopaixu(int* my_array, int len)
- {
- bool flag = false;
- for (int i = 0; i <len && !flag; ++i) {
- flag = true;
- for (int j = 1; j < len; ++j) {
- if ( my_array[j]> my_array[j - 1] ) {
- int temp = my_array[j];
- my_array[j] = my_array[j - 1];
- my_array[j - 1] = temp;
- flag = false;
- }
- }
- }
- }
3. 插入排序
默认对两个序列进行操作: 有序序列, 无序序列.
可以将无序序列分为两个部分
- void insert_paixu(int* my_array, int len)
- {
- int temp = 0;// 存储基准数
- int index = 0; // 存储坑的位置
- for (int i = 1; i <len; ++i) {
- temp = my_array[i];
- index = i;
- for (int j = i - 1; j>= 0; --j) {// 从后往前遍历
- if (temp < my_array[j]) {
- my_array[j + 1] = my_array[j];
- index = j;
- }
- else break;// 最后一个保存的是最大的元素, 此语句可以减少判断
- }
- my_array[index] = temp;
- }
- }
4. 希尔排序
先分组, 再对每组进行插入排序. 希尔排序是把记录按下标的一定增量分组, 对每组使用直接插入排序; 随着增量逐渐减少, 每组包含的关键词越来越多, 当增量减至 1 时, 整个文件恰被分为一组, 算法便终止;
来源: http://www.bubuko.com/infodetail-2943343.html