第一种:冒泡排序
冒泡排序遍历两次数组,时间复杂度On2,每一次用一个元素和后续其他所有元素比较,若是大小不符合预期则反转位置,具体实现代码如下:
#include <iostream>
#include <vector>
void Printf(const std::vector<int>&nums)
{
for(auto num:nums)
{
std::cout<<"num:"<<num<<std::endl;
}
}
void BubbleSort(std::vector<int>&nums)
{
for(int i = 0 ; i < nums.size() ; ++i)
{
for(int j = 0; j < nums.size()-1; ++j)
{
if(nums[j]<nums[j+1])
{
auto temp = nums[j];
nums[j] = nums[j+1];
nums[j+1] = temp;
}
}
}
}
int main()
{
std::vector<int> nums = {1,5,2,9,6,4,8,3,11,5};
auto temp1 = nums;
Printf(temp1);
BubbleSort(temp1); std::cout<<"after BubbleSort"<<std::endl; Printf(temp1);
}
第二种:选择排序
选择排序是按照从大到小或者从小到大的顺序,每次选择后续元素最大最小的值放在当前应该输入位置上,具体实现代码如下:
#include <iostream>
#include <vector>
void Printf(const std::vector<int>&nums)
{
for(auto num:nums)
{
std::cout<<"num:"<<num<<std::endl;
}
}
void SelectSort(std::vector<int>&nums)
{
auto max = 0;
int pos = 0;
for(int i = 0; i < nums.size()-1; ++i)
{
max = nums[i];
pos = i;
for(int j = i+1; j < nums.size(); ++j)
{
if(nums[j]>max)
{
max = nums[j];
pos = j;
}
}
nums[pos] = nums[i];
nums[i] = max;
}
}
int main()
{
std::vector<int> nums = {1,5,2,9,6,4,8,3,11,5};
// auto temp1 = nums;
// Printf(temp1);
// BubbleSort(temp1); std::cout<<"after BubbleSort"<<std::endl; Printf(temp1);
std::cout<<"---------------------------------------------------"<<std::endl;
auto temp2 = nums;
Printf(temp2);
SelectSort(temp2); std::cout<<"after SelectSort"<<std::endl; Printf(temp2);
}
三:插入排序
插入排序,一般也被称为直接插入排序。对于少量元素的排序,它是一个有效的算法 。插入排序是一种最简单的排序方法,它的基本思想是将一个记录插入到已经排好序的有序表中,从而一个新的、记录数增1的有序表。在其实现过程使用双层循环,外层循环对除了第一个元素之外的所有元素,内层循环对当前元素前面有序表进行待插入位置查找,并进行移动。
具体代码实现如下:
#include <iostream>
#include <vector>
void Printf(const std::vector<int>&nums)
{
for(auto num:nums)
{
std::cout<<"num:"<<num<<std::endl;
}
}
void InsertSort(std::vector<int>&nums)
{
int insertIndex,insertVal;
insertIndex= insertVal = 0;
for(int i = 1; i < nums.size(); ++i)
{
insertVal = nums[i];
insertIndex = i-1;
while(insertIndex>=0&&nums[insertIndex]<insertVal)
{
nums[insertIndex+1] = nums[insertIndex];
insertIndex--;
}
if(insertIndex + 1 != i)
{
nums[insertIndex + 1] = insertVal;
}
}
}
int main()
{
std::vector<int> nums = {1,5,2,9,6,4,8,3,11,5};
// auto temp1 = nums;
// Printf(temp1);
// BubbleSort(temp1); std::cout<<"after BubbleSort"<<std::endl; Printf(temp1);
std::cout<<"---------------------------------------------------"<<std::endl;
// auto temp2 = nums;
// Printf(temp2);
// SelectSort(temp2); std::cout<<"after SelectSort"<<std::endl; Printf(temp2);
auto temp3 = nums;
Printf(temp3);
InsertSort(temp3); std::cout<<"after InsertSort"<<std::endl; Printf(temp3);
}
第四种:快速排序