排序算法有哪些，哪些是稳定的排序算法

常见排序算法及稳定性

排序算法	平均时间复杂度	最坏情况	稳定性	适用场景
冒泡排序	$O(n^2)$	$O(n^2)$	稳定	小数据量，教学
选择排序	$O(n^2)$	$O(n^2)$	不稳定	小数据量
插入排序	$O(n^2)$	$O(n^2)$	稳定	小数据量，几乎有序
希尔排序	$O(n logn$~$n^2)$	$O(n^2)$	不稳定	中小规模数据
归并排序	$O(n logn)$	$O(n logn)$	稳定	大数据量，链表排序
快速排序	$O(n logn)$	$O(n^2)$	不稳定	大数据量，数组排序
堆排序	$O(n logn)$	$O(n logn)$	不稳定	大数据量，数组排序
计数排序	$O(n+k)$	$O(n+k)$	稳定	小范围整数排序
桶排序	$O(n+k)$	$O(n^2)$	稳定	浮点数排序，均匀分布
基数排序	$O(nk)$	$O(nk)$	稳定	大量整数或字符串

k表示数字/关键字的位数或范围大小

排序代码

以数组{5，2，9，1，5，6}为例进行排序

冒泡排序(稳定)

#include<iostream>

int main(){
    int arr[]={5,2,9,1,5,6};
    int n=sizeof(arr)/sizeof(arr[0]);
    for(int i=0;i<n;i++){
        for(int j=0;j<n-i-1;j++){
            if(arr[j]>arr[j+1])swap(arr[j],arr[j+1]);
        }
    }
    for(int i=0;i<n;i++)
        std::cout<<arr[i]<<" ";
}

```

```java

冒泡排序(稳定)

```

```go

```

### 选择排序(不稳定)

```cpp

```

```java

插入排序(稳定)

```

```go

```

### 希尔排序(不稳定)

```cpp

```

```java

归并排序(稳定)

```

```go

```

### 快速排序(不稳定)

```cpp

```

```java

堆排序(不稳定)

```

```go

```

### 计数排序(稳定)

```cpp

```

```java

桶排序(稳定)

```

```go

```

### 基数排序(稳定)

```cpp

```

```java