博客
关于我
排序算法
阅读量:555 次
发布时间:2019-03-09

本文共 4234 字,大约阅读时间需要 14 分钟。

#include 
using namespace std;// void InsertSort(int arr[]) {};// 直接插入排序void InsertSort(int arr[], int n) { int i, j, key; for (i = 1; i < n; i++) { key = arr[i]; for (j = i - 1; j >= 0; j--) { if (key < arr[j]) { arr[j+1] = arr[j]; } else { break; } } arr[j+1] = key; }}// 希尔排序:分组后的插入排序void ShellSort(int arr[], int n) { for (int dk = n/2; dk > 0; dk = dk/2) { int i, j, key; for (i = dk; i < n; i++) { key = arr[i]; for (j = i - dk; j >= 0; j--) { if (key < arr[j]) { arr[j+dk] = arr[j]; } else { break; } } arr[j+dk] = key; } }}// 冒泡排序void BubbleSort(int arr[], int n) { for (int i = 0; i < n-1; i++) { bool flag = false; for (int j = n-1; j > i; j--) { if (arr[j-1] > arr[j]) { swap(arr[j-1], arr[j]); flag = true; } } if (flag == false) { return; } }}// 堆排序// 首先排序成大顶堆void heapify(int arr[], int n, int i) { int lagest = i; int lson = 2 * i + 1; int rson = 2 * i + 2; if (lson < n && arr[lagest] < arr[lson]) { lagest = lson; } if (lson < n && arr[lagest] < arr[rson]) { lagest = rson; } while (lagest != i) { swap(arr[lagest], arr[i]); heapify(arr, n, lagest); }}// 排序入口void heap_sort(int arr[], int n) { for (int i = n /2 - 1; i >= 0; i++) { heapify(arr, n, i); } for (int i = n-1; i > 0; i--) { swap(arr[i], arr[0]); heapify(arr, i, 0); }}// 归并排序/*int low = 0, high = sizeof(arr)/sizeof(int);MergeSort(arr, low, high-1);*/void Merge(int arr[], int start1 , int end1, int start2, int end2) { int n1 = end1 - start1 + 1; int n2 = end2 - start2 + 1; int arr_left[n1], arr_right[n2]; for (int i = 0; i < n1; i++) { arr_left[i] = arr[start1 + i]; } for (int i = 0; i < n2; i++) { arr_right[i] = arr[start2 + i]; } int left = 0, right = 0; int p = start1; while (left < n1 && right < n2) { if (arr_left[left] < arr_right[right]) { arr[p] = arr_left[left]; left++; p++; } else { arr[p] = arr_right[right]; right++; p++; } } while (left < n1) { arr[p] = arr_left[left]; left++; p++; } while (right < n2) { arr[p] = arr_right[right]; right++; p++; }}void MergeSort(int arr[], int low, int high) { if(low < high) { // 此处比mid = (low + high)/2更好的防止内存泄漏 int mid = low + (high - low)/2; // 拆成左边和右边分别递归调用MergeSort MergeSort(arr, low, mid); MergeSort(arr, mid+1, high); // 合并 Merge(arr, low, mid, mid+1, high); }}// 直接选择排序void SelectSort(int arr[], int n) { for (int i = 0; i < n-1; i++) { int min = i; for(int j = i + 1; j < n; j++) { if (arr[j] < arr[min]) { min = j; } } if (min != i) { swap(arr[i], arr[min]); } }}// 快速排序/*选定pivot中心轴大于pivot放在他的右边小于pivot放在他的左边*/int Partition(int arr[], int low, int high) { int pivot = arr[low]; while(low < high) { while (low < high && arr[high] >= pivot) { high--; } arr[low] = arr[high]; while (low < high && arr[low] <= pivot) { low++; } arr[high] = arr[low]; } arr[low] = pivot; return low;}void QuickSort(int arr[], int low, int high) { if (low < high) { int pivotpos = Partition(arr, low, high); QuickSort(arr, low, pivotpos-1); QuickSort(arr, pivotpos + 1, high); }}int main() { int arr[6] = { 2, 1, 5, 4, 3, 8 }; int n = sizeof(arr) / sizeof(arr[0]); // InsertSort(arr, n); // ShellSort(arr, n); // heap_sort(arr, n); QuickSort(arr, 0, n-1); for(int i = 0; i < n; i++) { cout << arr[i] << endl; } return 0;}

转载地址:http://aukpz.baihongyu.com/

你可能感兴趣的文章
Mysql 数据库InnoDB存储引擎中主要组件的刷新清理条件:脏页、RedoLog重做日志、Insert Buffer或ChangeBuffer、Undo Log
查看>>
mysql 数据库中 count(*),count(1),count(列名)区别和效率问题
查看>>
mysql 数据库备份及ibdata1的瘦身
查看>>
MySQL 数据库备份种类以及常用备份工具汇总
查看>>
mysql 数据库存储引擎怎么选择?快来看看性能测试吧
查看>>
MySQL 数据库操作指南:学习如何使用 Python 进行增删改查操作
查看>>
MySQL 数据库的高可用性分析
查看>>
MySQL 数据库设计总结
查看>>
Mysql 数据库重置ID排序
查看>>
Mysql 数据类型一日期
查看>>
MySQL 数据类型和属性
查看>>
mysql 敲错命令 想取消怎么办?
查看>>
Mysql 整形列的字节与存储范围
查看>>
mysql 断电数据损坏,无法启动
查看>>
MySQL 日期时间类型的选择
查看>>
Mysql 时间操作(当天,昨天,7天,30天,半年,全年,季度)
查看>>
MySQL 是如何加锁的?
查看>>
MySQL 是怎样运行的 - InnoDB数据页结构
查看>>
mysql 更新子表_mysql 在update中实现子查询的方式
查看>>
MySQL 有什么优点?
查看>>