插入排序：算法思想
算法思想：每次将⼀个待排序的记录按其关键字⼤⼩插⼊到前⾯已排好序的⼦序列中， 直到全部记录插⼊完成。
步骤：引用来自菜鸟教程：https://www.runoob.com/data-structures/insertion-sort.html
-
第一轮：从第二位置的 6 开始比较，比前面 7 小，交换位置。
-
第二轮：第三位置的 9 比前一位置的 7 大，无需交换位置。
-
第三轮：第四位置的 3 比前一位置的 9 小交换位置，依次往前比较。
-
第四轮：第五位置的 1 比前一位置的 9 小，交换位置，再依次往前比较。
代码：
#include<iostream>
using namespace std;
#include<vector>
//插入排序
//插入排序是从第二个元素进行排序的，每次排序时。当前元素都会和前面的元素进行对比。
void insertSort(vector<int>& v) {
int temp;//临时存放当前元素
int j;
for (int i = 1; i < v.size(); i++) {
temp = v[i];//存放当前元素
//将当前元素和之前的元素进行对比
//即检查前面所有已经排好序的元素是否大于当前元素值
for (j = i - 1; j >= 0; j--) {
if (v[j] > temp)
v[j + 1] = v[j];//将大于temp的元素后移
else
break;
}
//可将上面的循环体改写为
//for (j = i - 1; j >= 0 && a[j - 1] > temp; j--) v[j + 1] = v[j];
v[j + 1] = temp;//将temp放入对应位置。注意：这里是j+1，因为再前面的循环条件中，j = j-1，不满足条件才会跳出循环
}
}
int main() {
vector<int> v = { 2,5,9,5,12,43,76,1,0,89};
insertSort(v);
for (vector<int> ::iterator it = v.begin(); it != v.end(); it++) {
cout << (*it) << " ";
}
cout << endl;
for (int i = 0; i < v.size(); i++) {
cout << v[i] << " ";
}
cout << endl;
system("pause");
return 0;
}
希尔排序
算法思想：希尔排序目的为了加快速度改进了插入排序，交换不相邻的元素对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。
见菜鸟教程：https://www.runoob.com/data-structures/shell-sort.html
冒泡排序算法思想：
基于“交换”的排序：根据序列中两个元素关键字的⽐较结果来对换这两个记录在序列中的位置。其目的是找到最大（最小）值，倒数第二大值，倒数第三大值....
算法为：
算法简介: 1.比较相邻的元素，前一个比后一个大（或者前一个比后一个小）调换位置
2.每一对相邻的元素进行重复的工作，从开始对一直到结尾对，这步完成后，结尾为做大或最小的数.
3.针对除了最后一个元素重复进行上面的步骤
4.重复1-3步骤直到完成排序
代码
void bubbleSort(vector<int>& v) {
for (int i = 0; i < v.size() - 1; i++) {
//每次从第1个元素开支找，一次找到最大值，倒数第二大值...
for (int j = 0; j < v.size()-1-i; j++) {
if (v[j] > v[j+1]) {//如果前面的大于后面的，将较大的值向后移动，直到选出最大的那个值
int temp = v[j];
v[j] = v[j + 1];
v[j + 1] = temp;
}
}
}
}
快速排序
随机化快速排序基本思想：算法思想：
1.通过一趟排序将要排序的数据分割成独立的两部分：分割点左边都是比它小的数，右边都是比它大的数。
2.然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
代码
//用第一个元素将待排序的子数组序列划分为左右连个部分
//并返回第一个元素最终放置的位置。左边部分元素比该元素小，
//右边的元素比该元素大。
int partition(vector<int>& v, int low, int high) {
//选取子数组的第一个元素作为基准元素
int pivot = v[low];
//用low和right所搜基准的最终文职
while (low < high)
{
while (low < high && v[high] >= pivot)
high--;//找到右边小于基准元素的值，并将其放置再low的左边
v[low] = v[high];//并将其放置在下标为low处
while (low < high && v[low] <= pivot)
low++;//找到左边大于基准元素的值
v[high] = v[low];
}
//当low == high时，其左边的值都比pivot小，右边的值都比pivot大
v[low] = pivot;
return low;//必须返回该值，告诉该元素放置的位置
}
//快速排序
void quickSort(vector<int>& v,int low,int high) {
if (low < high) {
//先对整个数组进行划分。有点类似对二叉树进行遍历。
int position = partition(v, low, high);
//再进行递归处理，分别对左边和右边的部分进行排序
quickSort(v, low, position-1);
quickSort(v, position + 1, high);
}
}
简单选择排序
选择排序：每一趙在待排序元素中选取关键字最小（或最大）的元素加入有序子序列.
简单选择排序是基于选择排序的,每⼀趟在待排序元素中选取关键字最⼩的元素加⼊有序⼦序列.有点类似冒泡排序.
算法:1.从待排序序列中，找到关键字最小的元素；
2. 如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换；
- 从余下的 N - 1 个元素中，找出关键字最小的元素，重复(1)、(2)步，直到排序结束。
代码
void selectSort(vector<int>& v) {
for (int i = 0; i < v.size(); i++) {
int min = i;//记录最小元素的位置
for (int j = i + 1; j < v.size(); j++) {//在v[i+1...v,size()]中选择最小元素的下标
if (v[j] < v[min])
min = j;//更新最小元素的位置
}
if (min != i) {//每一次都找出一个最小值，放在数组开头
int temp = v[min];
v[min] = v[i];
v[i] = temp;
}
}
}
京公网安备 11010502036488号