冒泡排序
排序思路
从数组第一个元素出发，和第二个元素作比较。如果第一个元素较大，就将其与第二个元素交换位置。遍历数组，那么最大的元素将出现在数组的最右侧，完成一遍排序；第二遍从数组第一个元素开始，执行相同的操作，这次遍历终点为 n - 1 ，以此类推。遍历终点为第二个数组元素后，停止遍历，排序算法完成。
代码如下：
#include <iostream>
#include <vector>
using namespace std;
void bubble(vector<int> &nums, int n)
{
for(int i = 0; i < n - 1; i++)
{
if(nums[i] > nums[i + 1])
{
swap(nums[i], nums[i + 1]);
}
}
}
vector<int> bubble_sort(vector<int> &nums, int n)
{
for(int i = n; i > 0; i--)
{
bubble(nums, i);
}
return nums;
}
int main()
{
vector<int> vec = {4,5,3,6,2,5,1};
for(int i = 0; i < vec.size(); i++)
{
cout << vec[i] << " ";
}
cout << endl;
cout << " ---------- " << endl;
bubble_sort(vec,7);
for(int i = 0; i < vec.size(); i++)
{
cout << vec[i] << " ";
}
return 0;
}
选择排序
排序思路
假设第一个元素为数组中最小的元素，从第二个元素开始遍历数组，找出剩余元素中最小的元素。找到这个元素后，将其与第一个元素比较，把更小的那个元素放在数组的第一位。之后以此类推。遍历终点为第 n - 1个元素后，停止遍历，选择排序算法完成。
代码如下：
int select_sort(vector<int> &arr)
{
int min_value = 0;
int min_pos = 0;
for(int i = 0; i < arr.size(); i++)
{
min_value = arr[i];
min_pos = i;
for(int j = i + 1; j < arr.size(); j++)
{
if(arr[j] < min_value)
{
min_value = arr[j];
min_pos = j;
}
}
}
if(arr[i] > min_value)
{
arr[min_pos] = arr[i];
arr[i] = min_value;
}
}
void main() {
vector<int> s;
vector.push_back(3);
vector.push_back(5);
vector.push_back(2);
vector.push_back(7);
vector.push_back(1);
vector.push_back(4);
select_sort(s);
for(vector<int> :: iterator it = arr.begin(); it != arr.end(); it++)
{
cout << *it << endl;
}
//return 0;
}
堆排序
排序思路
堆排序，本质上为构建一个完全二叉树，动态维护一个大顶堆/小顶堆，之后将根节点元素移动至完全二叉树的末尾，进行递归运算即可。
- 首先需要维护一个大顶堆。 大顶堆的定义为：根节点的值比所有子节点的值都要大。如果这三个节点顺序发生改变，则需要继续向下维护大顶堆。 设二叉树节点下标从0开始计数，目标节点下标为i，则它的双亲节点为(i - 1) / 2，左孩子节点为2i+1，右孩子节点为2i+2。
- 建堆的时间复杂度为O(n),排序的时间复杂度为O(nlogn)，因此堆排序的总体时间复杂度为O(nlogn)，空间复杂度为O(n)。
代码如下：
#include <iostream>
#include <vector>
using namespace std;
//vector<int> &arr好像不行，但arr[]就可以
//先维护一个大顶堆,维护的时间复杂度为O(logN)
void heapify(int arr[], int n, int i)
{
int largestNode = i;//将一个节点视为它和两个孩子的三者最大值
int lchild = 2 * i + 1; //左右孩子下标随之确定
int rchild = 2 * i + 2;
if (lchild < n && arr[lchild] > arr[largestNode])//如果左孩子没超出节点，且左孩子值大于i节点的值，就把最大值下标给左孩子
{
largestNode = lchild;
}
if (rchild < n && arr[rchild] > arr[largestNode])//右孩子同理
{
largestNode = rchild;
}
if (largestNode != i)//把上面的下标兑现，和节点交换位置。这是自下而上的递归，所以继续heapify.
{
swap(arr[largestNode], arr[i]);
heapify(arr, n, largestNode);//请注意递归条件——从这个最大节点开始遍历。
}
}
void heap_sort(int arr[], int n)
{
//堆排序分为建堆和排序两步
//首先建堆,从最后一个非叶子节点i开始，自下而上建堆
for (int i = n / 2 - 1; i >= 0; i--) //这里n是数组长度，所以最后一个节点下标为n-1,因此它的双亲节点为(n-1-1)/2
{
heapify(arr, n, i);//思考一下动态建堆过程，搞明白
}
//接下来开始排序
for (int j = n - 1; j > 0; j--)
{
swap(arr[j], arr[0]); //把大顶堆的顶和最后一个元素交换位置
heapify(arr, j, 0); //然后继续维护这个新的大顶堆
}
}
int main()
{
int arr[] = {5,6,3,4,1,7,2};
for (int i = 0; i < 7; i++)
{
cout << arr[i] << endl;
}
heap_sort(arr, 7);
for (int i = 0; i < 7; i++)
{
cout << arr[i] << endl;
}
}
- 思考：如果我想倒排数组，我需要怎么操作？
快速排序
排序思路
- 快速排序的思路为：先选定一个基准值，其所在下标为pivot；将所有小于这个基准值的元素移到pivot左边，将所有大于这个基准值的元素移到pivot右边。之后对pivot左侧和右侧的元素分别执行递归，最终可以得到一个升序排列的数组。
- 时间复杂度为O(nlogn),最坏情况为O(n) 由于没有引入额外的空间数组，因此空间复杂度为O(1)。
代码如下：
#include <iostream>
#include <vector>
using namespace std;
void quick_sort(vector<int> &nums, int left, int right)
{
int pivot = left;
if(left > right) return;
for(int i = left; i < right; i++)
{
if(nums[i] < nums[right])
{
swap(nums[i],nums[pivot]);
pivot++;
}
}
swap(nums[pivot], nums[right]);
quick_sort(nums, left, pivot - 1);
quick_sort(nums, pivot + 1, right);
}
int main()
{
vector<int> vec = {4,5,3,6,2,5,1};
for(int i = 0; i < vec.size(); i++)
{
cout << vec[i] << " ";
}
cout << endl;
cout << " ---------- " << endl;
quick_sort(vec, 0, 6);
for(int i = 0; i < vec.size(); i++)
{
cout << vec[i] << " ";
}
return 0;
}
插入排序
排序思路
- 扑克牌抽牌原理——将未排序的数组元素插入有序数组。 首先我们默认第一个数本身已经是有序数组，然后从第二个数开始往前插入。大的放左边，小的放右边。遍历到最后一个元素即可。
代码如下：
#include <iostream>
#include <vector>
using namespace std;
void insert_sort(vector<int> &nums, int n)
{
for(int i = 1; i < n; i++)
{
int temp = nums[i]; //注意这里是从1开始遍历，因此temp值是数组第二个元素，也是未排序的第一个元素
int j = i - 1; //j是左边已排好序的最大的数
while(j >= 0 && nums[j] >= temp) //边界条件
{
nums[j + 1] = nums[j];//如果有序数组最后一个元素 > 待插的元素，就把有序数组元素指针前移，直到小于待插元素为止。
j--;
}
nums[j + 1] = temp;//找到了，把元素插进来。
}
}
int main()
//测试用例
{
vector<int> arr = {4,5,3,6,2,5,1};
for(int i = 0; i < 6; i++)
{
cout << arr[i] << " ";
}
cout<< endl;
cout<< "----------" << endl;
insert_sort(arr, 7);
for(int i = 0; i < 6; i++)
{
cout << arr[i] << " ";
}
return 0;
}
归并排序
排序思路
简单来说就是先将数组内元素拆分为最小单元格，然后开辟一个新的数组空间，按大小顺序依次存储这些分散的元素。 形象解释——分治后合并
代码如下：(debug好像有问题…)
#include <iostream>
#include <vector>
using namespace std;
int tmp[10001] = { 0 };
void merge_sort(vector<int> a, int left, int right)
{
if(left >= right) return ;
int mid = left + (right - left) / 2;
merge_sort(a, left, mid);
merge_sort(a, mid + 1, right);
int i = left, j = mid + 1, cnt = 0;
while(i <= mid && j <= right)
{
if(a[i] <= a[j])
{
tmp[cnt++] = a[i++];
}
else
{
tmp[cnt++] = a[j++];
}
}
while(i <= mid)
{
tmp[cnt++] = a[i++];
}
while(j <= right)
{
tmp[cnt++] = a[j++];
}
for(int i = left, j = 0; i <= right; i++, j++)
{
a[i] = tmp[j];
}
}
int main()
{
vector<int> arr = {4,5,3,6,2,5,1};
//int arr[] = {4,5,3,6,2,5,1};
for(int i = 0; i < 7; i++)
{
cout << arr[i] << " ";
}
cout<< endl;
cout<< "--------------" << endl;
merge_sort(arr, 4 ,1);
for(int i = 0; i < 7; i++)
{
cout << arr[i] << " ";
}
return 0;
}
