数据结构与算法（二）排序
引言
数据结构与算法（一）数据结构分类与时间空间复杂度
上一节，我们简述了算法中数据结构、以及评判算法优劣的时间、空间复杂度，这一节我们将探讨计算机算法中一个常见的问题——排序。
排序
排序在平时开发中，是一个非常常见的一种需求，我们时常需要把一些数据元素经行一定秩序化的排列，这就意味着对排序经行更为优化的算法开发是十分有必要的。在工程经行算法编用的时候，我们会把每一个算法封装成一个API，然后再像调用jdk一样去使用。
Comparable接口
Comparable接口可使排序算法更具有通用性，无论是数据或是对象经行排序，我们都要提供一个排序的秩序规则，并要求这些物体较于排序规则而言是可比较的。
范例：
- 定义一个学生类Student，具有年龄age和姓名username两个属性，并通过Comparable接口提供比较规则；
- 定义测试类Test，在测试类中定义测试方法Comparable getMax(Comparable a,Comparable b)完成测试。
Sort.Student类
package Display.ComparableImplement.Sort;
//1. 定义一个学生类Student
//具有年龄age和姓名username两个属性
// 并通过Comparable接口提供比较规则；
public class Student implements Comparable<Student>{
private int age;
private String username;
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
public String getUsername() {
return username;
}
public void setUsername(String username) {
this.username = username;
}
@Override
public String toString() {
return "Student{" +
"age=" + age +
", username='" + username + '\'' +
'}';
}
@Override
public int compareTo(Student o) {
return this.getAge()-o.getAge();
}
}
Test.TestComparable
package Display.ComparableImplement.Test;
import Display.ComparableImplement.Sort.Student;
//2. 定义测试类Test
// 在测试类中定义测试方法Comparable getMax(Comparable a,Comparable b)完成测试。
public class TestComparable {
public static Comparable getMax(Comparable a,Comparable b){
//judge=a.age-b.age
//judge>0 a>b
//judge=0 a=b
//judge<0 a<b
int judge=a.compareTo(b);
if(judge>=0){
return a;
}else{
return b;
}
}
public static void main(String[] args) {
//创建两个Student对象
//调用getMax方法
Student a = new Student();
Student b = new Student();
a.setAge(18);
a.setUsername("李华");
b.setAge(19);
b.setUsername("李明");
Comparable max = getMax(a,b);
System.out.println(max);
}
}
输出结果：
这个实例就告诉我们，在我们之后所将接触到的排序问题，可以是数据，也可以是经过Comparable接口包装过的对象，我们就需要像上述过程一样使用Comparable接口来定义排序规则。
简单排序
冒泡排序
基本原理
冒泡排序是十分基础的排序方法，在我们学习C语言的时候，就已经了解了，所以，这里不再分析算法。其排序原理就是：
- 比较相邻元素。如果前一个元素比后一个大，就交换两者的位置；
- 对每一对相邻元素采取该做法，排到最后一个元素就可以确定为最大的元素；
- 在对依次从后往前（从大往小）确定排序关系。
所以我们可以预知到，这个算法中含有两层嵌套的循环，是平方阶型的时间复杂度，是为O(N2)。如下例：
import java.awt.*;
import java.util.Random;
import java.util.Scanner;
//冒泡排序
public class BubbleSort {
public static void BubbleSort(int sample[]){
int len = sample.length;
int temp=0;
for (int i = 0; i < len-2; i++) {
for (int j = 0; j < len-1; j++) {
if(sample[j]>sample[j+1]){
temp = sample[j];
sample[j] = sample[j+1];
sample[j+1] = temp;
}
}
}
for (int i = 0; i < len; i++) {
System.out.print(sample[i]+" ");
}
}
//实例测试
public static void main(String[] args) {
Random random = new Random();
int sample[] = new int[9];
Scanner reader = new Scanner(System.in);
for (int i = 0; i <9 ; i++) {
sample[i] = reader.nextInt();
}
BubbleSort(sample);
}
}
测试一组结果，如下：
上面就是简单利用冒泡排序算法对一个数组经行了大小排序，而我们为了增强其通用性，我们要把他写成API。
API设计
| 类名 | Bubble |
|---|---|
| 构造方法 | Bubble():创建Bubble对象 |
| 成员变量 | 1.public static void sort (Comparable[] a) :对数组内的元素进行排序 2.private static boolean greater(Comparable v,Comparable w):判断v是否大于w 3.private static void exch(Comparable[] a, int i, int j):交换a数组中，索引i 和索引j处的值。 |
代码：
public class Bubble {
//对数组内的元素进行排序
public static void sort (Comparable[] a){
for (int i = a.length-1; i >0 ; i--) {
//冒泡排序是从后向前排
for (int j = 0; j < i; j++) {
//比较索引j和索引j+1处的值
if(greater(a[j],a[j+1])){
exch(a,j,j+1);
}
}
}
}
//判断v是否大于w
private static boolean greater(Comparable v,Comparable w){
return v.compareTo(w)>0;
}
//交换a数组中，索引i 和索引j处的值。
private static void exch(Comparable[] a, int i, int j){
Comparable temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
性能分析
这里上面说了， 这是个双层嵌套的平方阶。所以时间复杂度是O(N2)。
选择排序
排序原理：
在序列中，选出合适的元素将其放置于合适的位置。
- 在每一次遍历的过程中，都假定第一个索引元素是最小元素，和其他索引出的值依次进行比较，如果当前索引处的值大于其他某个索引出的值，则更换假定值，继续比较直到比较完成。
- 交互元素将该元素放置到正确位置
- 继续排序其他位置
API设计
| 类名 | Selection |
|---|---|
| 构造方法 | Selection():创建Selection对象 |
| 成员变量 | 1.public static void sort (Comparable[] a) :对数组内的元素进行排序2.private static boolean greater(Comparable v,Comparable w):判断v是否大于w 3.private static void exch(Comparable[] a, int i, int j):交换a数组中，索引i 和索引j处的值。 |
代码
public class Selection {
//对数组内的元素进行排序
public static void sort (Comparable[] a){
for (int i = 0; i < a.length-2; i++) {
//从前往后排，最后一个可以不拍
int minIndex = i;
for (int j = i+1; j < a.length; j++) {
//需要比较最小索引i的值与
if(greater(a[minIndex],a[j])){
minIndex = j;
}
}
exch(a,i,minIndex);
}
}
//判断v是否大于w
private static boolean greater(Comparable v,Comparable w){
return v.compareTo(w)>0;
}
//交换a数组中，索引i 和索引j处的值。
private static void exch(Comparable[] a, int i, int j){
Comparable temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
性能分析
选择算法中核心计算部分的执行代码，也是拥有两层循环的结构，我们依照最坏情况分析，所以这个算法的时间复杂度仍然是O(N2)。
插入排序
算法原理
将元素分成两块，前一块为既定顺序列，后一块为待排顺序列，然后，不断的从代排顺序列中提取元素，加入到既定顺序列中去与既定顺序的元素意义比较，直至放置到相应的位置。
API设计
| 类名 | Insertion |
|---|---|
| 构造方法 | Insertion():创建Insertion对象 |
| 成员变量 | 1.public static void sort (Comparable[] a) :对数组内的元素进行排序2.private static boolean greater(Comparable v,Comparable w):判断v是否大于w 3.private static void exch(Comparable[] a, int i, int j):交换a数组中，索引i 和索引j处的值。 |
代码：
public class Insertion {
//对数组内的元素进行排序
public static void sort (Comparable[] a){
for (int i = 1; i < a.length; i++) {
for (int j = i; j > 0; j--) {
if(greater(a[j-1],a[j])){
exch(a,j-1,j);
}else{
break;
}
}
}
}
//判断v是否大于w
private static boolean greater(Comparable v,Comparable w){
return v.compareTo(w)>0;
}
//交换a数组中，索引i 和索引j处的值。
private static void exch(Comparable[] a, int i, int j){
Comparable temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
性能分析
依照分析最坏情况的原则，并且我们可以发现，插入排序是分为两块，并把元素插入在既定已排块中进行排序；而冒泡排序，同样是分为了两块，只是将元素放置在待排的区域里进行排序，以保证已排区域内的顺序原始正确性。但共通的是都经历了两层循环，用以调动其中一块并进行内部排序。所以插入排序的时间复杂度是和冒泡排序是一样的，都是O(N2)。
高级排序
希尔排序
希尔排序是一种特殊的插入排序，也可以说是插入排序的改良版本，也称“缩小增量排序”。
算法原理
- 选定一个增长量h，按照增长量h作为数据分组的依据，对数据进行分组
- 对分好的组的每一个组完成插入排序
- 减少增长量，重复步骤二，直至减少量为1
在这里增长量的不断减少并进行排序的过程就是一个不断析构扫描排序，将元素进一步的排至有序位置，运用了“分治”的思想，将插入排序进行了简化。
增量的选择
API设计
| 类名 | Shell |
|---|---|
| 构造方法 | Shell():创建Shell对象 |
| 成员变量 | 1.public static void sort (Comparable[] a) :对数组内的元素进行排序2.private static boolean greater(Comparable v,Comparable w):判断v是否大于w 3.private static void exch(Comparable[] a, int i, int j):交换a数组中，索引i 和索引j处的值。 |
代码：
public class Shell {
//对数组内的元素进行排序
public static void sort (Comparable[] a){
//确定增长量
int h = 1;
while(h < a.length/2){
h =h*2+1;
}
//进行希尔排序
while(h>=1){
//排序
//1.找到待插入的元素
for (int i = h; i < a.length; i++) {
//2.把待插入的元素插入到有序元素中
for (int j = i; j >= h ; j-=h) {
//代插入元素a[j]
//比较a[j]和a[j-h]
if(greater(a[j-h],a[j])){
//交换元素
exch(a,j-h,j);
}else{
//待插入元素已经找到了合适的位置，结束循环
break;
}
}
//减少h的值
}
h = h/2;
}
}
//判断v是否大于w
private static boolean greater(Comparable v,Comparable w){
return v.compareTo(w)>0;
}
//交换a数组中，索引i 和索引j处的值。
private static void exch(Comparable[] a, int i, int j){
Comparable temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
性能分析
对于希尔排序而言，其时间复杂度是与增长量的选取有关，上述链接中提供了不同增量的选取，而对于不同增量的时间复杂度，需要用到数论与组合数学的知识进行计算。
| 增量方式 | 时间复杂度 |
|---|---|
| 希尔增量 | O(N2) |
| Hibbard增量 | O(N3/2) |
| Sedgewick增量 | O(N4/3) |
注：使用Hibbard增量的希尔排序平均情形运行时间基于模拟的结果被认为是O(N5/4),只不过尚未证明（研究方向);Sedgewick增量最坏情形运行时间复杂度是O(N4/3),平均运行时间猜测为O(N7/6)。这是事前分析估算法。
对于这种分析需要较为高级的数学知识，及稳定性极弱的算法，我们一般采取事后估算分析：
按照之前事前估算分析的方法，
我先写一个数据记事本
import java.io.FileOutputStream;
import java.io.FileWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
public class FileWrite {
public static void main(String[] args) throws IOException {
OutputStreamWriter osw=new OutputStreamWriter(new FileOutputStream("path(输出文件的路径)"));
FileWriter fileWriter=new FileWriter("输出到文件",true);
for (int i = 1000000; i > 0 ; i--) {
osw.write(i+"\r\n");
}
osw.flush();
osw.close();
}
}
设置的一百万倒序数值，我们将正序排序。
import Display.Insertion;
import Display.Shell;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
public class SortCompare {
public static void main(String[] args) throws Exception{
//1.创建一个ArrayList集合，保存读取出来的整数
ArrayList<Integer> list = new ArrayList<>();
//2.创建缓存数据流BufferedReader,读取数据，并存储到ArrayList中
BufferedReader reader = new BufferedReader(new FileReader("输出文本路径"));
String line = null;
while((line=reader.readLine())!=null){
//line是字符串，把line转换为Integer，存储到集合中
int i = Integer.parseInt(line);
list.add(i);
}
//读取完毕后，关闭读取流
reader.close();
//3.把ArrayList集合转换成数组
Integer[] arr = new Integer[list.size()];
list.toArray(arr);
//4.调用测试代码完成测试
testInsertion(arr);
testShell(arr);
}
/**
* 测试希尔排序
*/
public static void testShell(Integer[] a){
//1.获取代码执行之前的时间
long start = System.currentTimeMillis();
//2.运行算法代码
Shell.sort(a);
//3.获取执行之后的时间
long end = System.currentTimeMillis();
//4.计算执行总时间
System.out.println("Shell algorithm costs"+(end-start)+"ms");
}
/**
* 测试插入排序
*/
public static void testInsertion(Integer[] a){
//1.获取代码执行之前的时间
long start = System.currentTimeMillis();
//2.运行算法代码
Insertion.sort(a);
//3.获取执行之后的时间
long end = System.currentTimeMillis();
//4.计算执行总时间
System.out.println("Insertion algorithm costs"+(end-start)+"ms");
}
}
插入算法：
希尔算法：
我们就可以十分清晰的发现这两种算法在较高输入规模下的优劣。
归并排序
递归
在定义方法时，在方法内部调用方法本身，例如：
public void show(){
System.out.println("a");
show();
}
作用：
它通常把一个大型复杂的问题，层层转换一个与原问题问题相似，规模较小的问题来求解。递归策略只需要少量的程序就可以描述解题过程所需要的多次重复计算，大大的减少了程序的代码量。
注意：
在递归中，我们无限调用该方法，必须要有边界条件，能够让递归结束。因为每一次递归调用都会在栈内存中开辟新的空间，重新运行方法。如果递归层级太深，很容易造成栈溢出。
例如：阶乘计算
阶乘计算
1！ = 1
2！ = 2 * 1
3！ = 3 * 2 * 1
·
n！ = n * (n-1) * … * 1
代码：
public class Test {
public static void main (String[] args) throws Exception {
int result = factorial(5);
System.out.println(result);
}
//
public static int factorial(int n){
if (n==1){
return 1;
}
return n*factorial(n-1);
}
}
算法原理
归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的案例。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为：二路归并。
如上图
总体流程如下:
- 先把数据进行不停的对半分开，直至分为单个元素。
- 然后进行比较排序，
- 再将有序的数据串有序归并起来
归并流程如下:
- 载入两个指针分别从头读取有序待归并数据串，
- 并比较这两指针所指向的值，将较小的排至辅助数组对应位值，
- 然后，指针向后移动，继续比较。直至将全部数据归并为有序队列
- 将辅助数组传给原始数组。
API设计
| 类名 | Merge |
|---|---|
| 构造方法 | Merge():创建Merge对象 |
| 成员方法 | 1.public static void sort (Comparable[] a) :对数组内的元素进行排序2.private static void sort(Comparable[] a,int lo, int hi):对数组a中从索引o到索引hi之间的元素进行排序3.private static void merge(Comparable[] a,int lo,int mid,int hi):从索引lo到索引mid为一个子组，从索引mid+1到索引hi为另一个子组，把数组a中的这两个子组的数据合并成一个有序的大组（从索引lo到索引hi）4.private static boolean less(Comparable v, Comparable w):判断v是否小于w 5.private static void exch(Comparable[] a, int i, int j) :交换a数组中，索引i和索引j处的值。 |
| 成员变量 | 1.private static Comparable[] assist : 完成归并操作所需的辅助数组 |
代码：
public class Merge {
//归并所需辅助数组
private static Comparable[] assist;
//对数组内的元素进行排序
public static void sort (Comparable[] a){
//1.初始化辅助数组 assist
assist = new Comparable[a.length];
//2.定义lo变量，和hi变量，分别记录数组中最小的索引和最大索引
int lo = 0;
int hi = a.length-1;
//3.调用sort重载方法完成数组a中，从索引lo到索引hi的元素的排序
sort(a,lo,hi);
}
//对数组a中从索引o到索引hi之间的元素进行排序
private static void sort(Comparable[] a,int lo, int hi){
//安全性校验
if (hi <= lo){
return;
}
//对lo到hi之间的数据进行分组
int mid = lo+(hi-lo)/2;
//分别对每一组数据进行排序
sort(a,lo,mid);
sort(a,mid+1,hi);
//再把两个组中的数据进行归并
merge(a,lo,mid,hi);
}
//从索引lo到索引mid为一个子组
// 从索引mid+1到索引hi为另一个子组
// 把数组a中的这两个子组的数据合并成一个有序的大组（从索引lo到索引hi）
private static void merge(Comparable[] a,int lo,int mid,int hi){
//定义三个指针
int Aptr = lo;
int Bptr = mid+1;
int Cptr = lo;
//遍历，移动p1指针和p2指针，比较对应索引处的值
//找出小的那个，放到辅助数组的对应索引处
while(Aptr <= mid && Bptr <= hi){
//比较对应索引处的值
if(less(a[Aptr],a[Bptr])){
assist[Cptr++] = a[Aptr++];
}else{
assist[Cptr++] = a[Bptr++];
}
}
//遍历，如果p1的指针没有走完
//那么顺序移动p1指针，把对应指针放到辅组数组的对应索引处
while(Aptr <= mid){
assist[Cptr++] = a[Aptr++];
}
//遍历，如果p2的指针没有走完
//那么顺序移动p2指针，把对应指针放到辅组数组的对应索引处
while(Bptr <= hi){
assist[Cptr++] = a[Bptr++];
}
//把辅助数组中的元素拷贝到原数组中
for (int index = lo; index <= hi; index++) {
a[index] = assist[index];
}
}
//判断v是否小于w
private static boolean less(Comparable v, Comparable w){
return v.compareTo(w)<0;
}
//交换a数组中，索引i和索引j处的值。
private static void exch(Comparable[] a, int i, int j){
Comparable temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
性能分析
时间复杂度分析
归并排序，分为拆分和归并两个部分。
我们以上图8个元素为例说明：
8个元素：
- 每次对半拆分，共拆分log(2)8次，即3次
- 拆分3次即有3层，每一层数据串长度为：8/2k个元素,即：2(3-k)个元素,每一层数据串数：2k个
- 所以，每层比较次数=每层数据串长度*每次数据串数，即：2k*23-k=23
- 故3层共：3*23
推广到n:
- 每次对半拆分，共拆分log(2)n次
- 拆分log(2)n次即有log(2)n层，每一层数据串长度为：n/2k个元素,即：2log(2)n-k 个元素,每一层数据串数：2k个
- 所以，每层比较次数=每层数据串长度*每次数据串数，即：2k*2log(2)n-k=2log(2)n=n
- 故层log(2)n共：n*log(2)n
- 根据大O记法法则，最后归并排序时间复杂度记为：O(NlogN)
**注意：**在这里，虽然理论上归并排序的时间复杂度是O(n log n)，但是在算法进行辅助数组内数据来回拷贝这些其他处理时，会严重放慢排序的速度，导致很难运用到主存排序当中去。当然，这种拷贝我们通过在递归交替层次时审慎地转换a和assist的角色得到避免，或者使用规避排序的另一种变形也可以非递归的实现。但是，对于重要的内部排序应用，人们还是会选择快速排序。
空间复杂度分析
在进行归并排序中，我们需要额外申请数组空间（辅助数组），导致空间复杂度提升，是典型的以空间换时间的算法操作。
快速排序
算法原理
如名可知，快速排序是在实践中最快的已知排序算发。同归并排序一样，快速排序也是一种分治的递归算法。
与归并不同的是，快速排序分为两块而治的分界点是枢纽元(pivot)，例如上例：
- 选定第一个元素作为枢纽元，将小于枢纽元的元素放置在其左边，大于的放置在其右边
- 再通过递归，对两侧的元素如法炮制，选定一个枢纽元，进行分治
- 直到分治出的元素组中只有两个元素，停止递归，将这些有序元素组，进行逆向拼装组合一起。
下列是具体的切分方式：
- 首先，定义两个指针：left初始为0；right初始为hi+1
- 先从右往左搜索，right指针往左移动搜索，直至找到比枢纽元小的元素后停止
- 再从左往右搜索，left指针往右移动搜索，直至找到比枢纽元大的元素后，交换left索引处的值和right索引处的值
- 继续循环执行第二步，从右搜索，再从左搜索。
- 当左右指针相遇时，即left>=right指针，证明所有元素已被扫描完毕，将枢纽元与该两指针重合共同指向的值经行交换，一次切分过程结束。
API设计
| 类名 | Quick |
|---|---|
| 构造方法 | Quick():创建Quick对象 |
| 成员方法 | 1.public static void sort (Comparable[] a) :对数组内的元素进行排序2.private static void sort(Comparable[] a,int lo, int hi):对数组a中从索引o到索引hi之间的元素进行排序3.private static void partition(Comparable[] a,int lo,int hi):对数组a中，从索引lo到索引hi之间的元素进行分组，并返回分组界限对应的索引（枢纽元）4.private static boolean less(Comparable v, Comparable w):判断v是否小于w 5. private static void exch(Comparable[] a, int i, int j) :交换a数组中，索引i和索引j处的值。 |
public class Quick {
//对数组内的元素进行排序
public static void sort(Comparable[] a){
int lo = 0;
int hi = a.length-1;
sort(a,lo,hi);
}
//对数组a中从索引o到索引hi之间的元素进行排序
private static void sort(Comparable[] a,int lo, int hi){
//安全性校验
if(hi <= lo){
return;
}
//需要对数组中lo索引到hi索引处的元素进行分组
//左子组、右子组
int partition = partition(a, lo, hi);
//返回的是分组的分界值（枢纽元）位置变黄后的所在索引
//让左子组有序 lo--partition-1
sort(a,lo,partition-1);
//让右子组有序 partition+1--hi
sort(a,partition+1,hi);
}
//从对数组a中，从索引lo到索引hi之间的元素进行分组，并返回分组界限对应的索引（枢纽元）
private static int partition(Comparable[] a, int lo, int hi){
//确定枢纽元
Comparable pivot = a[lo];
//定义两个指针，left初始为0；right初始为hi+1
int left = lo;
int right = hi+1;
//切分
while(true){
//先从右向左扫描，移动right指针，找到一个比枢纽元小的元素，停止
while(less(pivot,a[--right])){
if (right ==lo){
break;
}
}
//再从左向右扫描，移动left指针，找到一个比枢纽元大的元素，停止
while (less(a[++left],pivot)){
if (left == hi){
break;
}
}
//判断 left>=right
//如果是，则元素扫描完毕，结束扫描
//如果不是，则交换元素
if (left >= right){
break;
}else{
exch(a,left,right);
}
}
//将枢纽元(就是第一个元素)的值和两指针重合共同指向的值交换
exch(a,lo,right);
return right;
}
//判断v是否小于w
private static boolean less(Comparable v, Comparable w){
return v.compareTo(w)<0;
}
//交换a数组中，索引i和索引j处的值。
private static void exch(Comparable[] a, int i, int j){
Comparable temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
性能分析
快速排序与归并排序异同
相同点：
- 快速排序和归并排序都是运用分治思想，先分再治。
- 两个排序均是利用到递归的算法
不同点：
- 归并排序是将数组分为两个子数组，并分别排序，再将有序的子数组（子数组内部有序，子数组外部之间无序）归并后得到整个数组的排序；快速排序是当被分为两块的数组都有序时（子数组内部、外部之间均有序），整个数组就自然有序了。
- 归并排序，一个数组是被均分为两组；快速排序，一个数组是由枢纽元切分为两组
时间复杂度
其时间复杂度是由切分选择处（枢纽元）的选择有关，在最好的情况下，其时间复杂度是O(N logN);在最坏的情况下，其设计复杂度是O(N2)。虽然，这样但是我们只要在枢纽元的选取上稍作努力，我们是可以保证快速排序时间复杂度维持在O(N log N)。
枢纽元的选取
排序的稳定性
定义
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的;否则称为不稳定的。
意义
当我们对一类元素经行多次排序，在第一次排序完成后，进行第二次排序（不同指标、特征的排序），在有相同的元素时，稳定的排序算法不会交换这两给相同的值，从而保护了第一次排序的顺序。
常见排序算法的稳定性
