sort排序

std::sort( )函数是库函数提供的排序函数，必须包括头文件#include <algorithm>，它使用的排序方法是类似于快排的方法，时间复杂度为n*log2(n)

Sort函数有三个参数：（第三个参数可不写）

  • 第一个是要排序的数组的起始地址。
  • 第二个是结束的地址（最后一位要排序的地址）
  • 第三个参数是排序的方法，可以是从大到小也可是从小到大，还可以不写第三个参数，此时默认的排序方法是从小到大排序。

C++代码示例

  1. 升序排序
    例如：数组a[5]={4,3,2,1,7}进行升序排列
sort(a,a+5) //数组的下标从0开始，数组名代表数组的首地址。5代表数组的长度
  1. 降序排序
    例如：数组a[5]={4,3,2,1,7}进行降序排列，直接可以写成：
sort(a,a+4,cmp) ; //cmp不能省略，需要自行实现该函数
  1. cmp函数的实现方式：
    如果后面的数比前面的数大，则
bool cmp( int a, int b ){<!-- -->
  return a>b; //降序排列，如果升序排列，则改为return a<b;
}

sort代码示例

#include <algorithm>
using namespace std;

 void printArray(int *a, int len)
 {
     for (size_t i = 0; i < len; i++) printf("%d\n", a[i]);     
 }
int main()
{
    int a[] = {4,1, 2, 3, 5,7, 6};
    sort(a, a+7);
    printArray(a, 7);

    printf("降序排序：\n");
    sort(a, a+7, [](int a, int b){return a > b;});
    printArray(a, 7);
}

冒泡排序

冒泡排序算法思想：
1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数，然后将该数固定
3.针对所有的元素重复以上的步骤，除了最后一个。
4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较

冒泡排序示例代码

 void swap(int *a, int i, int j)
 {<!-- -->
     int b = a[i];
     a[i] = a[j];
     a[j] = b;
 }
 
 void printArray(int *a, int len)
 {<!-- -->
     for (size_t i = 0; i < len; i++) printf("%d\n", a[i]);     
 }
 
//冒泡排序
void mpSort(int *a, int len)
{<!-- -->
    for (size_t i = 0; i < len - 1; i++) //第i轮排序
    {<!-- -->
        for (size_t j = 0; j <  len - i - 1; j++)  //这里len-i-1, 表示每一轮都会把最大的找出来移动到末尾，所以不用把`len-i- 1`后的数也进行比较
        {<!-- -->
            if (a[j] > a[j+1]) swap(a, j, j+1);
        }
    }
}
int main()
{<!-- -->
    int a[] = {<!-- -->4,1, 2, 3, 5,7, 6};
    mpSort(a, 7);
    printArray(a, 7);
}

快速排序

分治法的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。

使用递归，则需要找到递归点和递归出口：

  • 递归点：如果数组的元素大于1，就需要再进行分解，所以我们的递归点就是新构造的数组元素个数大于1
  • 递归出口：我们什么时候不需要再对新数组不进行排序了呢？就是当数组元素个数变成1的时候，所以这就是我们的出口。

快速排序示例代码:

 void printArray(int *a, int len)
 {<!-- -->
     for (size_t i = 0; i < len; i++) printf("%d\n", a[i]);     
 }
//快速排序
void quickSort(int *a, int left, int right)
{<!-- -->
    int i = left;
    int j = right;
    if (i > j) return;

    int base = a[i];
    while (i < j)
    {<!-- -->
        while (i < j && a[j] > base) j--; //分治法，从右往左找，找到比base小的数，赋值给a[i]
        if (i < j) a[i] = a[j];

        while (i < j && a[i] < base) i++;//分治法，从左往右找，找到比base大的数，赋值给a[j]
        if (i < j) a[j] = a[i];
    }

    a[i] = base;//base左边是比base小的数，base右边是比base大的数
    quickSort(a, left, i-1);//分治递归左边
    quickSort(a, i+1, right);//分治递归右边
    
}

int main()
{<!-- -->
    int a[] = {<!-- -->4,1, 2, 3, 5,7, 6};
    quickSort(a, 7);
    printArray(a, 7);
}

插入排序

插入排序(InsertionSort)，一般也被称为直接插入排序。

对于少量元素的排序，它是一个有效的算法。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增 1 的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动。

  • 基本思想：每一步将一个待排序的数据插入到前面已经排好序的有序序列中，直到插完所有元素为止。
  • 插入排序的平均时间复杂度也是 O(n^2)，空间复杂度为常数阶 O(1)，具体时间复杂度和数组的有序性也是有关联的。
  • 插入排序中，当待排序数组是有序时，是最优的情况，只需当前数跟前一个数比较一下就可以了，这时一共需要比较 N-1次，时间复杂度为 O(N)。最坏的情况是待排序数组是逆序的，此时需要比较次数最多，最坏的情况是 O(n^2)。

示例代码:

//插入排序
void insertSort(int *a, int len)
{<!-- -->
    for (int i = 1; i < len; i++)
    {<!-- -->
        int j;
        int x = a[i];       //每趟将a[i]插入到前面的排序子序列中
        for (j = i-1; j >= 0 && x < a[j]; j--)
        {<!-- -->
            a[j+1] = a[j];  //将前面较大的元素向后移动
        }
        a[j+1] = x;         //x值到达插入位置
    }
}
int main()
{<!-- -->
    int a[] = {<!-- -->4,1, 2, 3, 5,7, 6};
    xzSort(a, 7);
    insertSort(a, 7);
}

选择排序

选择排序法（以从小到大排序为例） 算法思想：

  • A.在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
  • B.从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾
  • C.以此类推，直到所有元素均排序完毕

选择排序示例代码

 void printArray(int *a, int len)
 {<!-- -->
     for (size_t i = 0; i < len; i++)  printf("%d\n", a[i]);
 }
//选择排序
void xzSort(int *a, int len)
{<!-- -->
    int tmp, min;
    for (int i = 0; i < len; i++)
    {<!-- -->
        min = i;
        for (int j = i+1; j < len; j++)
        {<!-- -->
            if (a[min] > a[j]) min = j;  //获取最小值索引
        }
        tmp = a[i];
        a[i] = a[min];  //交换索引为i和min的位置。
        a[min] = tmp;   //交换索引为i和min的位置。
    }
}
int main()
{<!-- -->
    int a[] = {<!-- -->4,1, 2, 3, 5,7, 6};
    xzSort(a, 7);
    printArray(a, 7);
}

--完--