算法读书笔记第2章-1

第二章的主要内容：一些排序算法，同时我会补充一些没有介绍的算法，本篇介绍三种基础的排血算法

（1）冒泡排序（ps:补充一个最简单的排序）

① 基本思想：顾名思义，冒泡就是像水泡一样向上升，所以方法就是从数组的第一个元素开始向后比较，遇到比自己小的就交换，否则不交换，直到最后

② 核心代码：

for(int i = n - 1; i > 0; i--)
    for（int j = 0; j < i;j++）
        if(a[j] > a[j+1])
            swap(a[j],a[j+1]);

③ 时间复杂度：O（n^2）因为两层比较

④ 额外空间复杂度：O（1），并没有申请额外的空间，只使用几个变量

⑤ 稳定，并没有交换元素的相对位置

#include<bits/stdc++.h>
using namespace std;

void BubbleSort(int a[],int n)
{
    for(int i=n-1; i> 0; i--)
    {
        for(int j=0; j < i; j++)
        {
            if(a[j] > a[j+1])
                swap(a[j],a[j+1]);
        }
    }
}

int main()
{
    int a[5] = {0,9,5,8,3};  BubbleSort(a,5);
    printf("%d",a[0]);  for(int i = 1; i < 5; i++)  {  printf(" %d",a[i]);  }
    return 0;
}

（2）选择排序

① 基本思想：第一次在0~n-1中选择min放在a[0]，第二次在1~n-1中选择min放在a[1],以此类推。

② 核心代码：

Way1：

for(int i = 0;i < n; ++i){
    int Mindex = i;
    for(int j = i; j < n; ++j){
        Mindex = a[j] < a[Mindex] ? j : Mindex;
    }
    swap(a[i],a[Mindex]);
}

Way 2：

for(int i = 0; i < n-1; ++i)
    for(int j = i+1; j < n; ++j)
        if(a[j] < a[i])
            swap(a[i],a[j]);

③ 时间复杂度：O（n^2）

④ 额外空间复杂度：O（1）

⑤ 不稳定，可能会交换元素的相对位置

1) 例子：5,4,5,1,2 第一次遍历的时候第一个5会和1交换，那它和第二个5的相对位置已经发生了改变

#include<bits/stdc++.h>
using namespace std;

//selectSort1.0
void SelectSort_1(int a[], int n)
{
    for(int i = 0; i < n-1; i++)
    {
        int minIndex = i;
        for(int j = i+1; j < n; j++)
        {
          minIndex = a[j] < a[minIndex] ? j : minIndex;
        }
        swap(a[i],a[minIndex]);
    }
}

//selectSort2.0
void SelectSort_2(int a[], int n)
{
    for(int i = 0; i < n - 1; i++)
        for(int j = i+1; j < n; j++)
            if(a[j] < a[i])
                swap(a[i],a[j]);
}
int main()
{
    int a[5] = {0,9,5,8,3};
    int b[5] = {0,9,2,7,4};  SelectSort_1(a,5);
    SelectSort_2(b,5);

    printf("a[]: ");
    printf("%d",a[0]);  for(int i = 1; i < 5; i++)  {  printf(" %d",a[i]);  }
    puts("");
    printf("b[]: ");  printf("%d",b[0]);  for(int i = 1; i < 5; i++)  {  printf(" %d",b[i]);  }
    return 0;
}

（3）插入排序

① 基本思想：遍历数组元素，选定一个固定的数，假如选择第一个数为X，遇到的数和其比较，若 <= X，不动，否则交换

② 核心代码：

for(int i = 1; i < n; ++i)
    for(j = i-1; j >=0; --j)
        if(a[j] > a[j+1])
            swap(a[j],a[j+1]);

③ 时间复杂度：O（n^2）

④ 额外空间复杂度：O（1）

⑤ 稳定

#include<bits/stdc++.h>
using namespace std;

void InsertSort(int a[], int n)
{
    for(int i = 1; i < n; i++)
        for(int j = i-1; j >= 0; j--)
            if(a[j] > a[j+1])
                swap(a[j],a[j+1]);
}

int main()
{
    int a[5] = {0,9,5,8,3};  InsertSort(a,5);
    printf("%d",a[0]);  for(int i = 1; i < 5; i++)  {  printf(" %d",a[i]);  }
    return 0;
}