排序算法-基础

一、冒泡排序

1、相邻元素比较

2、比较所有，直到一头

空间复杂度O(1),原址排序

时间复杂度O(n*n)

二、快速排序（quickSort）

1、定义

快速排序是一种分治算法，其核心思想是通过选择一个基准元素，将数组划分为两个子数组，其中一个子数组的元素都小于或等于基准元素，另一个子数组的元素都大于基准元素，然后对这两个子数组分别进行快速排序，直到整个数组有序。

2、方案：

1、找出基准值

2、数组左边一部分小于基准值

3、数组右边一部分大于基准值

4、递归分解、归并

3、其中找基准值（pivot)

1、左右指针法

1、左右指针

2、比较交换

2、for循环

左边第一个作为基准值

左端到指针都小于基准值

当前值与指针交换

4、空间复杂度O(1),时间复杂度O(nlogn)进行logn轮，每轮都是n次

三、归并排序

归并排序（Merge Sort）是一种经典的分治算法，它将数组分成两部分，分别排序，然后再将它们合并成一个有序的数组

1、原数组一分为二

2、合并两个有序数组

第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置

第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

重复步骤3直到某一指针超出序列尾

将另一序列剩下的所有元素直接复制到合并序列尾

3、递归

时间复杂度O(nlogn）

四、插入排序（insertSort）

一、从牌桌上一张一张拿到手里，成顺序形态

1、定义数组大小

2、查找插入元素位置

3、元素移位，留位置

4、插入位置

二、手里有一副牌，抽放成顺序形态

1.从第一个元素开始，该元素可以认为已经被排序；

2.取出下一个元素，在已经排序的元素序列中从后向前扫描；

3.如果该元素（已排序）大于新元素，将该元素移到下一位置；

4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；

5.将新元素插入到该位置后;

三、插入排序特性

1、空间原址性O(1)

2、时间复杂度O(n*n)

3、最好情况O(n)

四、插入排序的几张图

1、使用插入排序，排序手中的扑克牌

解读：斗地主的时候，桌面上的牌，拿到手中，7是桌面的牌

2、一个简单伪代码实例

五、计数排序（ CountingSort）

一、计数排序是一种基于非比较的排序算法，适合用于对整数范围有限的数组进行排序。它的时间复杂度为 O(n + k)，其中 n 是待排序数组的长度，k 是数组中元素的取值范围。

1、只用于整形，同时利用了数组索引代表数值的想法

2、通过数组索引代表数值

3、数组大小最大数最小数差

3、数组值标示元素出现的次数，有可能有相同的元素

二、缺点：

1、计数排序：思想很巧妙，适用范围具有局限性(整型数据)

2、序列中最大值和最小值之间的差值不能过大，这主要是防止建立数组时造成内存的浪费。

时间复杂度：O(N+range);非常块，但是数据范围很大的就差些，说明它适用于范围集中一组整型数据排序。

代码实例

六、基数排序&桶排序（Radix Sort）

t它是一种基于“位”（digit）分布的非比较排序算法，适用于整数或字符串的排序。Radix Sort 通常通过逐位处理（从最低位到最高位，或从最高位到最低位）来排序元素，常与 Counting Sort 结合使用。

1. 基数的作用：

? 基数排序的核心思想是按位排序，从最低位到最高位（LSD，Least Significant Digit），或者从最高位到最低位（MSD，Most Significant Digit）。

? 每一位的取值范围由基数决定，因此“基数”是这个算法的关键属性之一。

2. 多轮排序：

? 每一轮排序是基于当前位（个位、十位、百位等）进行的，而这些位的取值范围是基数的所有可能值。

? 通过逐位排序，将数据最终排成有序。

3. 对“基数”的依赖：

? 不同的数据类型（整数、字符串等）对应的基数不同，基数决定了排序的分组过程和效率。

4、时间复杂度

O(d(n+k))

5、基数

基数排序”（Radix Sort）之所以得名，是因为它的排序过程依赖于数据的“基数”（radix），也就是每个数字或字符串中每一位的可能取值范围。例如：

? 对于十进制整数来说，基数是 10（0 到 9）。

? 对于二进制数来说，基数是 2（0 和 1）。

? 对于英文字母（如字符串排序），基数是 26（A 到 Z 或 a 到 z）。