首先了解一下
插入排序:
从第一个元素开始 视前i个元素已经排好序
从第i个元素往下找 比第i个元素小的元素: 第j个元素
找到了第j个元素:遍历前i个元素(从后往前遍历) 直到找到比第j个元素小的元素 将第j个元素插入到这个元素的后面 比第j个元素大的元素整体后移一位 i++
- #include
- using namespace std;
- void InsertSort(int arr[],int nLen)
- {
-
-
- if (arr == NULL || nLen <= 1)
- return;
-
-
-
- for (int i=1;i
- {
- int temp = arr[i];
- int j = i-1;
- while (j >= 0 && arr[j] > temp)
- {
- arr[j + 1] = arr[j];
- j--;
- }
- arr[j + 1] = temp;
-
-
-
- }
-
-
-
- }
- int main()
- {
- int arr[10] = { 0,5,8,3,9,1,4,7,3,10 };
- InsertSort(arr, 10);
- for (int val : arr)
- {
- cout << val<<" ";
- }
- return 0;
- }
计数排序:
首先我们遍历arr 找出最大值Max和最小值Min
新开辟出一个数组arrtemp用来存arr中的元素出现的次数
其中 arrtemp的长度为Max-Min+1
把arrtemp的每一个元素都赋值0
再次遍历arr 把arr的相关元素信息存到arrtemp中:
arrtemp的下标代表 arr元素的值-Min
arrtemp元素的值代表 当前 值为 (arrtemp元素下标 +Min) 的元素在arr中出现的次数
遍历计数数组arrtemp 把其中的值再次赋值回到arr
- #include
- using namespace std;
-
- //重复数据多时:
- //用计数排序
- void CountSort(int arr[], int nLen)
- {
-
-
- if (arr == NULL || nLen <= 1)
- return;
-
- //遍历数组找打最大值和最小值
- int Max = arr[0];
- int Min = arr[0];
-
-
- for (int i = 0; i < nLen; i++)
- {
- if (arr[i] > Max)
- {
- Max=arr[i];
- }
- if (arr[i] < Min)
- {
- Min = arr[i];
- }
-
- }
- //根据最大值和最下小值 开辟计数数组
- int* arrtemp = new int[Max - Min + 1];
- //为技术数组中的每一项都赋为0
- ::memset( arrtemp,0,sizeof(int)*(Max - Min + 1 ));
-
- //记录arr中每个元素出现的次数 并记录在arrtemp计数数组中
- //arr的元素-Min=他在arrtemp中的下标
-
- // arrtemp元素为 在arr中 值为 当前arrtemp的下标的元素 在arr中出现次数
- for (int i = 0; i < nLen; i++)
- {
- arrtemp[arr[i]-Min]++;
- }
- //重新往arr里赋值 j为下标
- int j = 0;
-
- //遍历arrtemp 往arr里放他的下标
- for (int i = 0; i < Max - Min + 1; i++)
- {
- //通过元素个数判断放几次
- while (arrtemp[i] != 0)
- {
- arr[j] = i + Min;
- j++;
- arrtemp[i]--;
- }
-
- }
-
- //释放计数数组
- delete arrtemp;
-
-
-
-
- }
- int main()
- {
- int arr[10] = { 0,0,2,2,2,1,4,7,3,10 };
- CountSort(arr, 10);
- for (int val : arr)
- {
- cout << val << " ";
- }
- return 0;
- }
3.快速排序
这里我们先了解一下思想
快速排序中用到了二分排序的思想
挖坑填补法
首先将首元素定义为标准数
在条件begin>end下
循环
将首元素arr[begin]挖出来 在末尾元素arr[end]往前找比标准数小的元素
找到了把找到的元素给坑(arr[begin])
没找到
end--
再从arr[begin]往后找比标准值大的元素
找到了 填坑 (arr[begin]赋给arr[end])
没找到
begin++
这是一次二分查找
此时我们的标准值的左面的元素都小与标准值 右边都大于标准值
我们用递归在将左侧和右侧分别二分查找 最终 数组就被排好序了
- #include
- using namespace std;
-
- //快速排序
-
- int Partition(int arr[], int begin, int end)
- {
- //首元素挖坑
- int mid=arr[begin];
-
- //首元素为标准值
-
- //遍历 loop
- while (begin
- {
- //在后边往前找比标准值小的
- //填入坑
- while (begin
mid) - {
-
- end--;
-
- }
- arr[begin] = arr[end];
-
- //在填入的坑的位置往后找比标准值大的
- //填入后边的坑
- while (begin < end&&arr[begin] <= mid)
- {
- begin++;
-
- }
- arr[end] = arr[begin];
-
-
- }
- arr[begin] = mid;
- return begin;
-
- return mid;
- //将标准值返回
- }
- void QuickSort(int arr[], int begin, int end)
- {
- if (arr == NULL || begin >=end)
- {
- return;
-
- }
- int mid = Partition(arr,begin,end);
- QuickSort(arr, begin, mid - 1);
- QuickSort(arr, mid + 1, end);
-
-
-
- }
- int main()
- {
- int arr[10] = { 0,0,2,2,2,1,4,7,3,10 };
- QuickSort(arr, 0,9);
- for (int val : arr)
- {
- cout << val << " ";
- }
- return 0;
- }
-
相关阅读:
Shell-条件控制语句2
十大排序算法
【浅学Java】从浏览器中输入一个URL之后,会发生什么?
打破原则引入SQL,MongoDB到底想要干啥?
技术分享| anyRTC音视频混流技术解析
【排序算法】冒泡排序
【前端验证】通关寄存器与ral_model —— 将寄存器描述由excel格式转为xml格式的脚本
Android热修复Sophix的使用
集合Collection
Kotlin中Any、Nothing、Unit 类型的概念和用法
-
原文地址:https://blog.csdn.net/van9527/article/details/126146323