动图演示：
https://www.cnblogs.com/onepixel/articles/7674659.html
冒泡排序
#include <bits/stdc++.h> //偷懒的写法，不过编译时间比较久，包含大部分头文件
#include <algorithm>
#include <vector>
bubble_sotr(vector<int> &arr)
{
for(int i=0 ; i< arr.size()-1; i++)
{
bool flag = false;
for(int j = 0;j < arr.size()-i;j++)
{
if(arr[j]>arr[j+1])
{
//int temp = arr[j];
//arr[j]= arr[j+1];
//arr[j+1] = temp;
swap(arr[j],arr[j+1]);
flag = true;
}
}
if(!falg) //冒泡排序的优化
break;
}
}
//选择排序
select_sort1(vector<int> &arr)
{
for(int i=0; i < arr.size();i++)
{
for(int j=i+1;j<arr.size();j++)
{
if(arr[i]<arr[j])//把最小的数取出来放到第一个位置
swap(arr[i],arr[j]);
}
}
}
void select_sort2(vector<int> &arr)
{ int min_index = 0;
for(int i=0; i < arr.size();i++)
{
for(int j=i+1;j<arr.size();j++)
{
if(arr[j]<arr[min_index])//把最小的数取出来放到第一个位置
min_index = j; //保留最小数的索引
}
swap(arr[i],arr[min_index]);//把最小数放到对应的前面
}
}
给定一个序列。如果使用冒泡排序，需要swap多少次？
插入排序： 原理和玩扑克差不多。
前面的牌是有序的
void insert_sort(vector<int> &arr)
{
for(int i = 1; i<arr.size();i++)
{
int temp = arr[i];
for(int j=i-1;j >= 0;j--)
{
if(arr[i]<arr[j])
{
arr[j+1]=arr[j];
}else{
break;//这个地方很重要，如果这个数与前一个数相比，比前一个数大，那么他的位置就不需要移动
}
}
arr[j+1]=temp;
}
}
//希尔排序 缩小增量排序（不稳定）
void shell_sort(vector<int> &arr)
{
算法思想：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序
将一组数字，按步长为3/n分为一组，分为3组。每一组按插入排序，每组的下标间隔为g步长
第二次按步长为2分为2组，每组按插入排序
第三次按步长为1，按插入排序。
}
int main()
{
int n;
vector<int> arr;
cin >> n;
for(int i=0,t;i<n;i++)
{
cin >> t;
arr.push_back(t);
}
bubble_sotr(arr);
for(auto x:arr)
cout<< x <<' ';
cout<<endl;
}
https://www.cnblogs.com/chenxiwenruo/p/8529525.html
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
#include <cstdlib>
#include <ctime>
using namespace std;
//----------------插入排序--------------------------
void insertSort(int a[],int len){
for(int i=1;i<len;i++){
int tmp=a[i];
int j=i-1;
while(j>=0 && tmp<a[j]){
a[j+1]=a[j];
j--;
}
a[j+1]=tmp;
}
}
//----------------选择排序--------------------------
void selectSort(int a[],int len){
for(int i=0;i<len-1;i++){
int minidx=i;
for(int j=i+1;j<len;j++){
if(a[j]<a[minidx]){
minidx=j;
}
}
if(a[i]>a[minidx]){
int tmp=a[i];
a[i]=a[minidx];
a[minidx]=tmp;
}
}
}
//----------------冒泡排序--------------------------
void bubbleSort(int a[],int len){
int tmp;
for(int i=0;i<len-1;i++){
bool flag=true;
for(int j=0;j<len-i-1;j++){
if(a[j]>a[j+1]){
tmp=a[j+1];
a[j+1]=a[j];
a[j]=tmp;
flag=false;
}
}
if(flag)
break;
}
}
//----------------归并排序O(NlgN)--------------------------
#define INF 0x3f3f3f3f
/*
将[l,mid]和[mid+1,r]两个区间进行合并，每次取两个开头最小的那个
*/
void merges(int a[],int l,int mid,int r){
int len1=mid-l+1;
int len2=r-mid;
int L[len1+1],R[len2+1];
for(int i=0;i<len1;i++)
L[i]=a[l+i];
for(int i=0;i<len2;i++)
R[i]=a[mid+1+i];
L[len1]=INF;
R[len2]=INF;
int left=0,right=0;
for(int k=l;k<=r;k++){
if(L[left]<=R[right]){
a[k]=L[left];
left++;
}
else{
a[k]=R[right];
right++;
}
}
}
//对区间[l,r]进行归并排序
void mergeSort(int a[],int l,int r){
if(l<r){
int mid=(r+l)/2;
mergeSort(a,l,mid);
mergeSort(a,mid+1,r);
merges(a,l,mid,r);
}
}
//----------------快速排序O(NlgN)--------------------------
/*
以最后a[r]为划分点，将数组a划分成两个部分
前部分<=a[r],后部分>a[r]
最后返回a[r]的索引
*/
int quick_partition(int a[],int l,int r){
int x=a[r];
int i=l-1;
for(int j=l;j<r;j++){
if(a[j]<=x){
i++;
swap(a[i],a[j]);
}
}
swap(a[i+1],a[r]);
return i+1;
}
void quickSort(int a[],int l,int r){
if(l<r){
int mid=quick_partition(a,l,r);
quickSort(a,l,mid-1);
quickSort(a,mid+1,r);
}
}
int main()
{
int num=10;
int a[num];
srand((unsigned)time(NULL));
for(int i=0;i<num;i++){
a[i]=rand()%20;
printf("%d ",a[i]);
}
printf("\n");
quickSort(a,0,num-1);
for(int i=0;i<num;i++){
printf("%d ",a[i]);
}
return 0;
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
