01.选择排序
基本思想
- 每一趟 (例如第 i 趟,i = 0, 1, …,n-2)在后面 n-i个待排的数据元素中选出关键字最小的元素, 作为有序元素序列的第 i 个元素。
排序过程
- 首先通过n-1次关键字比较,从n个记录中找出关键字最小的记录,将它与第一个记录交换
- 再通过n-2次比较,从剩余的n-1个记录中找出关键字次小的记录,将它与第二个记录交换
- 重复上述操作,共进行n-1趟排序后,排序结束
- 代码实现
#include <iostream>
#include <vector>
using namespace std;
void SelectSort(vector<int>& intArray, int array_size)
{
//选择排序思路 数组中的第一个元素和剩余的数组元素分别比较 如果第一个元素大于其他数组元素
//交换值 一轮下来 可以确定数组中的最小(最大)值 二轮下来 确定 次最小(最大)值
for (int i = 0; i < array_size - 1; i++)
{
for (int j = i + 1; j < array_size; j++)
{
int temp;
if (intArray[i] > intArray[j])
{
temp = intArray[i];
intArray[i] = intArray[j];
intArray[j] = temp;
}
}
}
}
int main() {
vector<int> intArray{ 1,4,2,9,5,6 };
int array_size = intArray.size();
SelectSort(intArray, array_size);
for (auto& a : intArray)
{
cout << a << " ";
}
return 0;
}
02.插入排序
基本思路
- 整个排序过程为n-1趟插入,即先将序列中第1个记录看成是一个有序子序列,然后从第2个记录开始,逐个进行插入,直至整个序列有序
- 实质:对线性表执行n-1次插入操作,只是先要找到插入位置
- V[0], V[1], …, V[i-1]已经排好序。这时已经排好序。这时,用V[i]的关键字与V[i-1], V[i-2], …的关键字进行比较, 找到插入位置即将V[i]]插入, 原来位置上的对象向后顺移。
插入排序关键点:
- 拿出一个元素,留出位置
- 符合条件的元素后移
- 代码实现
#include <iostream>
#include <vector>
using namespace std;
void Inert_Sort(vector<int>& arry, int len)
{
int i, j;
for (i = 1; i < len; ++i)
{
int temp = arry[i];
for (j = i - 1; j >= 0; --j)
{
if (temp < arry[j])
{//在有序列表中比temp值大的元素后羿
arry[j + 1] = arry[j];
}
else { break; }//temp大于有序表中的最后一位则不需要移动
}
arry[j + 1] = temp;//跳出内层循环后插入在合适的位置
}
}
int main() {
vector<int> intArray{ 1,4,2,9,5,6 };
int array_size = intArray.size();
Inert_Sort(intArray, array_size);
for (auto& a : intArray)
{
cout << a << " ";
}
return 0;
}
03.冒泡排序
排序过程
- 将第一个记录的关键字与第二个记录的关键字进行比较,若为逆序r[1].key>r[2].key,则交换;然后比较第二个记录与第三个记录;依次类推,直至第n-1个记录和第n个记录比较为止——第一趟冒泡排序,结果关键字最大的记录被安置在最后一个记录上。
- 对前n-1个记录进行第二趟冒泡排序,结果使关键字次大的记录被安置在第n-1个记录位置
- 重复上述过程,直到“在一趟排序过程中没有进行过交换记录的操作“为止。
- 代码实现
#include <iostream>
#include <vector>
using namespace std;
void Bubble_Sort(vector<int>& arry,int len)
{
for (int i = 0; i < len; i++)
{
for (int j = i+1; j < len; j++)
{
if (arry[j] < arry[j-1])
{
int tmp = arry[j];
arry[j] = arry[j-1];
arry[j-1] = tmp;
}
}
}
}
int main() {
vector<int> intArray{ 1,4,2,9,5,6 };
int array_size = intArray.size();
Bubble_Sort(intArray, array_size);
for (auto& a : intArray)
{
cout << a << " ";
}
return 0;
}
04.希尔排序
排序过程
- 先取一个正整数d1<n,把所有相隔d1的记录放一组,组内进行直接插入排序;然后取d2<d1,重复上述分组和排序操作;直至di=1,即所有记录放进一个组中排序为止
- O(nlogn)
- 希尔排序是
不稳定
的。
- 代码实现
#include <iostream>
#include <vector>
using namespace std;
void Shell_Sort(vector<int>& array, int n) //a -- 待排序的数组, n -- 数组的长度
{
int i, j, gap; // gap为步长,每次减为原来的一半。
for (gap = n / 2; gap > 0; gap /= 2)
{
// 共gap个组,对每一组都执行直接插入排序
for (i = 0; i < gap; i++)
{
for (j = i + gap; j < n; j += gap)
{
// 如果a[j] < a[j-gap],则寻找a[j]位置,并将后面数据的位置都后移。
if (array[j] < array[j - gap])
{
int tmp = array[j];
int k = j - gap;
while (k >= 0 && array[k] > tmp)
{
array[k + gap] = array[k];
k -= gap;
}
array[k + gap] = tmp;
}
}
}
}
}
int main() {
vector<int> intArray{ 1,4,2,9,5,6 };
int array_size = intArray.size();
Shell_Sort(intArray, array_size);
for (auto& a : intArray)
{
cout << a << " ";
}
return 0;
}
05.快速排序
基本思路
- 快速排序是对冒泡排序的一种改进。
- 通过一躺排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,基准数据排在这两个子序列的中间。
- 然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
#include <iostream>
#include <vector>
using namespace std;
int partition(vector<int>& a, int p, int r) {
int key = a[r];//取最后一个
int i = p - 1;
for (int j = p; j < r; j++)
{
if (a[j] <= key)
{
i++;
//i一直代表小于key元素的最后一个索引,当发现有比key小的a[j]时候,i+1 后交换
int temp1 = a[j];
a[j] = a[i];
a[i] = temp1;
}
}
int temp2 = a[r];
a[r] = a[i + 1];
a[i + 1] = temp2;
return i + 1;
}
void Quick_Sort(vector<int>& a, int p, int r) {
int position = 0;
if (p < r)
{
position = partition(a, p, r);//返回划分元素的最终位置
Quick_Sort(a, p, position - 1);//划分左边递归
Quick_Sort(a, position + 1, r);//划分右边递归
}
}
int main() {
vector<int> intArray{ 1,4,2,9,5,6 };
int array_size = intArray.size();
Quick_Sort(intArray, 0,array_size-1);
for (auto& a : intArray)
{
cout << a << " ";
}
return 0;
}
//单路快排
#include <iostream>
#include <vector>
using namespace std;
int partition(vector<int>& vec,int l,int r){
swap(vec[r],vec[rand()%(r-l+1)+l]); //优化
int key = vec[r];
int i=l-1;
for(int j=l;j<r;j++){
if(vec[j] <= key){
i++;
swap(vec[i],vec[j]);
}
}
i++;
swap(vec[i],vec[r]);
return i;
}
void Quick_Sort(vector<int>& vec,int l,int r){
int p = 0;
if(l < r){
srand(time(NULL)); //优化
p = partition(vec,l,r);
Quick_Sort(vec,l,p-1);
Quick_Sort(vec,p+1,r);
}
}
int main() {
vector<int> intArray{ 1,4,2,9,5,6 };
int array_size = intArray.size();
Quick_Sort(intArray, 0,array_size-1);
for (auto& a : intArray)
{
cout << a << " ";
}
return 0;
}
//双路快排
#include <iostream>
#include <vector>
using namespace std;
int partition2(vector<int>& vec,int l,int r){
swap(vec[l],vec[rand()%(r-l+1)+l]); //优化
int key = vec[l];
int i = l+1, j = r;
while(true){
while(i <= r && vec[i] < key)i++;
while(j >= l+1 && vec[j] > key)j--;
if(i>j)break;
swap(vec[i],vec[j]);
i++;
j--;
}
swap(vec[l],vec[j]);
return j;
}
void Quick_Sort2(vector<int>& vec,int l,int r){
int p = 0;
if(l < r){
srand(time(NULL)); //优化
p = partition2(vec,l,r);
Quick_Sort(vec,l,p-1);
Quick_Sort(vec,p+1,r);
}
}
int main() {
vector<int> intArray{ 1,4,2,9,5,6 };
int array_size = intArray.size();
Quick_Sort2(intArray, 0,array_size-1);
for (auto& a : intArray)
{
cout << a << " ";
}
return 0;
}
//三路快排
#include <iostream>
#include <vector>
using namespace std;
void Quick_Sort3(vector<int>& vec,int l,int r){
if(l < r){
srand(time(NULL)); //优化
swap(vec[l],vec[rand()%(r-l+1)+l]); //优化
int key = vec[l];
int lt = l;
int gt = r+1;
int i = l+1;
while(i<gt){
if(vec[i] < key){
swap(vec[i++],vec[++lt]);
}
else if(vec[i] > key){
swap(vec[i],vec[--gt]);
}
else{
++i;
}
}
swap(vec[l],vec[lt]);
Quick_Sort3(vec,l,lt-1);
Quick_Sort3(vec,gt,r);
}
}
int main() {
vector<int> intArray{ 1,4,2,9,5,6 };
int array_size = intArray.size();
Quick_Sort3(intArray, 0,array_size-1);
for (auto& a : intArray)
{
cout << a << " ";
}
return 0;
}
06.归并排序
算法思路
- 比较a[i]和b[j]的大小,若a[i]≤b[j],则将第一个有序表中的元素a[i]复制到r[k]中,并令i和k分别加上1。否则将第二个有序表中的元素b[j]复制到r[k]中,并令j和k分别加上1。
- 如此循环下去,直到其中一个有序表取完。
- 然后再将另一个有序表中剩余的元素复制到r中下标k到下标t的单元。
- 代码实现
#include <iostream>
#include <vector>
using namespace std;
void merge(vector<int>& arr, int L, int mid, int R)
{
vector<int> help(R - L + 1,0);
int p1 = L, p2 = mid + 1, i = 0;
while (p1 <= mid && p2 <= R)
{
help[i++] = arr[p1] > arr[p2] ? arr[p2++] : arr[p1++];
}
while (p1 <= mid)
help[i++] = arr[p1++];
while (p2 <= R)
help[i++] = arr[p2++];
for (int i = 0; i < R - L + 1; i++)
{
arr[L + i] = help[i];
}
}
void sortprocess(vector<int>& arr, int L, int R)
{
if (L < R)
{
int mid = L + ((R - L) >> 1); // (L+R)/2
sortprocess(arr, L, mid);
sortprocess(arr, mid + 1, R);
merge(arr, L, mid, R);
}
}
void Merge_Sort(vector<int>& arr, int L, int R)
{
if (arr.size() < 2)
return;
sortprocess(arr, L, R);
}
int main() {
vector<int> intArray{ 1,4,2,9,5,6 };
int array_size = intArray.size();
Merge_Sort(intArray, 0,array_size-1);
for (auto& a : intArray)
{
cout << a << " ";
}
return 0;
}
评论已关闭