算法分类
1、排序
- 比较类排序
2、复杂度
相关概念
- 稳定：如果 a 本来在 b 前面，而a = b ，排序之后 a 仍然在 b 的前面
- 不稳定：如果 a 本来 在b的前面，而 a = b ，排序之后 a 可能在 b 的后面
- 时间复杂度：对排序数据的总的操作数，反映当 n 变化时，操作次数呈什么变化
- 空间复杂度： 指算法计算机内执行时所需存空间的度量，也是数据规模 n 的函数
几种常见排序(已学)
1、冒泡排序(Bubble Sort)
~~注：重复地走访序列，一次比较两个元素，如果顺序错误就交换过来，重复地进行直到没有再需要交换，也就说该数列排序完成------->这个算法的名字是因为越小的元素会经由交换慢慢“浮”到顶端
动图展示
代码实现
function bubbleSort(arr) {
var len = arr.length;
for (var i = 0; i < len - 1; i++) {
for (var j = 0; j < len - 1 - i; j++) { //每次循环最大的元素都被放到最后，就不用管了
if (arr[j] > arr[j+1]) { // 相邻元素两两对比
var temp = arr[j+1]; // 元素交换
arr[j+1] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}
课上讲的模板类写法：
template<class T>
void mySwap(T &x,T &y)
{
T temp = x;
x = y;
y = temp;
}
template<class T>
void bubbldeSort(T a[],int n)
{
int i= n-1 ;
while(i>0){
int lastExchange = 0;//每次都值为 0 ，如果下面的 if语句 不成立，退出循环，说明排序完成
//(a[j]<a[j+1])都成立
for(int j=0;j<i;j++)
if(a[j+1]<a[j])
{
mySwap(a[j],a[j+1]);
lastExchange = j; //第一次循环这个 j = n-1，a[j+1]包括后面的数就不用管了
}
i = lastExchange;
}
}
2、选择排序(Selection Sort)
~~注：首先在未排序序列中找到最小(大)的元素，存放到排序序列的起始位置，然后再从剩余未排序序列元素中继续寻找最小元素，然后放到已排序序列的末尾。以此类推，直到排序完毕。
动图
](https://imgchr.com/i/aItpqJ)
代码实现;
function selectionSort(arr) {
var len = arr.length;
var minIndex, temp;
for (var i = 0; i < len - 1; i++) {
minIndex = i; //记录未排序的第一个数，方便后面最小的数与其交换
for (var j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) { // 寻找最小的数
minIndex = j; // 将最小数的索引保存
}
}
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp; //将 i 和最小的数交换 ，然后 i 往后移一位，前面是已经排好的序列
}
return arr;
}
3、插入排序
~注：描述--->
- 第一个元素已经排序
- 取出下一个元素，在已经排序的元素序列中从后往前扫描
- 如果该元素(已排序)大于新元素，将该元素移至下一个位置
- 重复3，直到找到已排序的元素小于或等于新元素的位置
代码实现：
function insertionSort(arr) {
var len = arr.length;
var preIndex, current;
for (var i = 1; i < len; i++) {
preIndex = i -1;
current = arr[i]; //前面的数都是已经排好序的
while (preIndex >= 0 && arr[preIndex] > current) { //后面的数比前面的大就循环，如果小于或等于就停止循环，进行插入
arr[preIndex + 1] = arr[preIndex]; //往后挪位置
preIndex--;
}
arr[preIndex+1] = current; //上面arr[preIndex]往后移了，此时arr[preIndex]为无用值，又减了一，所以要加1；
}
return arr;
}
//注释1：从下标为1的元素开始遍历，记作temp-->然后从temp向前遍历将元素往后挪位，直到不满足条件插入此元素
c++模板类写法：
template<class T>
void insertionSort(T a[],int n)
{
int i,j;
T temp;
for(int i=1;i<n;i++)
{
int j=i;
T temp = a[i];
while(j>0 && temp<a[j-1])
{
a[j]=a[j-1]; //这里j值并没有改变，下面减去一才是要填充的位置
j--;
}
a[j]=temp; //a[j-1]被移动到后面的序列去了， j-1是无用数据
}
}
3 2 5 4 9 8 7 temp = 2
2 3 5 4 9 8 7 temp = 5
2 3 4 5 9 8 7 temp = 5
//注释2：从下标为1开始循环(因为要j-1不能越界)，如果前面的元素比temp(循环选定元素)大，说明要后退一位，以便留一个位置给temp，就这样一直后移直到找到一个数 < temp
4、计数排序
适用于在较小范围内的数字；
- 计数排序可以不用进行比较两数大小的操作
- 另外用一个数组记录出现数字的次数，下标表示数字，数组下标对应的元素表示该数字出现的次数
#include<bits/stdc++.h>
using namespace std;
void countSort(vector<int>& array){
int max = array[0];
for(int i=1;i<array.size();i++){// 找出最大值
if(array[i]>max){
max = array[i];
}
}
vector<int> countArray(max+1); // 容量为max+1
for(int i=0;i<array.size();i++){
countArray[array[i]]++;
}
int index = 0;// countArray下标代表数字，对应的元素值表示
//出现的次数
================================
for(int i=0;i<countArray.size();i++){
for(int j=0;j<countArray[i];j++){
array[index++] = i;
// 直接修改原数组(参数)
================================
}
}
}
int main(){
vector<int> a={4,4,6,5,3,2,8,1,7,5,6,0,10};
countSort(a);
for(vector<int>:: iterator it = a.begin();it!=a.end();it++ ){
cout<<*it<<endl;
}
return 0;
}
5、快速排序
- 基准元素
- 两边向中间循环查找
双边循环
#include <iostream>
#include <vector>
#define N 10
using namespace std;
void sawp(int &a,int &b)// 交换两个数
{
int temp;
temp = a;
a = b;
b = temp;
}
void quickSort(int left,int right,vector<int> & a)
{
if(left >= right)
return;
int i,j,base;
i = left, j =right;
base = a[left];// 基准元素
while(i < j)
{
while(a[j]>=base && i < j) //i <j 基本条件
j--;
while(a[i]<=base && i < j)
i++;
if(i < j) // 有可能此时i==j
swap(a[i],a[j]); //交换左边和右边的值，一个大于基准值，一个小于基准值
}
a[left] = a[i];
a[i] = base;
quickSort(left,i-1,a);//对剩余的部分进行快速排序
quickSort(i+1,right,a);//
}
y总模板
#include <iostream>
using namespace std;
const int N = 1000010;
int q[N];
void quick_sort(int q[], int l, int r)
{
if (l >= r) return;
int i = l - 1, j = r + 1, x = q[l + r >> 1];
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j) swap(q[i], q[j]);
}
quick_sort(q, l, j);
quick_sort(q, j + 1, r);
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
quick_sort(q, 0, n - 1);
for (int i = 0; i < n; i ++ ) printf("%d ", q[i]);
return 0;
}
单边循环>
#include <iostream>
#include <vector>
#define N 10
using namespace std;
void sawp(int &a, int &b) { // 交换两个数
int temp;
temp = a;
a = b;
b = temp;
}
void quickSort(vector<int> &a, int L, int R) {
if(L>=R){
return; // 递归结束条件
}
// L,R表示起始和终点下标
int p = a[L];
int mark = L;
for (int i = L + 1; i <= R; i++) {
if (a[i] < p) {
cout<<p<<" > "<<a[i]<<endl;
cout<<"mark值为"<<mark<<endl;
mark++;
cout<<"mark值为"<<mark<<endl;
swap(a[mark], a[i]); //此时mark表示a[mark]>p,把小的
// 提到前面来
}
}
swap(a[mark], a[L]);
quickSort(a, L, mark - 1);
quickSort(a, mark + 1, R);
}
int main() {
vector<int> a = {4,7,3,5,6,2,8,1};
quickSort(a, 0, a.size() - 1);
for (int i = 0; i < a.size(); i++) {
cout << a[i] << " ";
}
return 0;
}