目录

1.基本概念

两种基本操作：

三种待排序存储方式

2.插入排序

直接插入排序

1.时间复杂度

2.空间复杂度

3.算法稳定性

 希尔排序

注意：

3.交换排序

冒泡排序（Bubble Sort）

原理：

时间复杂度：

快速排序：

算法描述

平均时间复杂度O(nlog n)

缺点：不稳定

4.选择排序

直接选择排序

【概述】

【排序过程】

堆排序

算法描述

5.归并排序

6.分配排序

箱排序：

基数排序：取多次关键字排序

7.内部排序方法比较

---

1.基本概念

按给定的关键字递增/递减的次序排列

两种基本操作：

• 比较两个关键字大小
• 改变指向记录的指针或移动记录本身

三种待排序存储方式

• 顺序存储
• 链式存储
• 辅助表形式

2.插入排序

直接插入排序

1.时间复杂度

最好情况就是全部有序，此时只需遍历一次，最好的时间复杂度为O ( n ) 
最坏情况全部反序，内层每次遍历已排序部分，最坏时间复杂度为O(n^2)

综上，因此直接插入排序的平均时间复杂度为 O(n^2)

2.空间复杂度

辅助空间是常量
平均的空间复杂度为：O (1)

3.算法稳定性

相同元素的前后顺序是否改变

直接插入排序是稳定的

 希尔排序

希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止

注意：

最后一个增量必须是1 ！！！

3.交换排序

冒泡排序（Bubble Sort）

原理：

每一趟只能确定将一个数归位。即第一趟只能确定将末位上的数归位，第二趟只能将倒数第 2 位上的数归位，依次类推下去。如果有 n 个数进行排序，只需将 n-1 个数归位，也就是要进行 n-1 趟操作。

而 “每一趟 ” 都需要从第一位开始进行相邻的两个数的比较，将较大的数放后面，比较完毕之后向后挪一位继续比较下面两个相邻的两个数大小关系，重复此步骤，直到最后一个还没归位的数。

代码：

//冒泡排序两两比较的元素是没有被排序过的元素--->
public void bubbleSort(int[] array){
    for(int i=0;i1;i++){//控制比较轮次，一共 n-1 趟
        for(int j=0;j1-i;j++){//控制两个挨着的元素进行比较
            if(array[j] > array[j+1]){
                int temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
            }
        }
    }
}

时间复杂度：

时间复杂度为 O(n^2)

快速排序：

算法描述

快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。执行如下操作：

从数列中挑出一个元素，称为 “基准”（pivot）；
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
 

平均时间复杂度O(nlog n)

缺点：不稳定

4.选择排序

直接选择排序

【概述】

直接选择排序又称简单选择排序，是一种不稳定的排序方法，其是选择排序中最简单一种，其基本思想是：第 i 趟排序再待排序序列 a[i]~a[n] 中选取关键码最小的记录，并和第 i 个记录交换作为有序序列的第 i 个记录。

其实现利用双重循环，外层 i 控制当前序列最小值存放的数组元素位置，内层循环 j 控制从 i+1 到 n 序列中选择最小的元素所在位置 k

【排序过程】

1.排序过程
具体的排序过程为：

将整个记录序列划分为有序区和无序区，初始时有序区为空，无序区含有待排序的所有记录
在无序区选择关键码最小的记录，将其与无序区中的第一个元，使得有序区扩展一个记录，同时无序区减少了一个记录
不断重复步骤 2，直到无序区只剩下一个记录为止
2.实例
 初始关键字：『 8，5，2，6，9，3，1，4，0，7 』

 第一趟排序后：0，『5，2，6，9，3，1，4，8，7』

 第二趟排序后：0，1，『2，6，9，3，5，4，8，7』

 第三趟排序后：0，1，2，『6，9，3，5，4，8，7』

 第四趟排序后：0，1，2，3，『9，6，5，4，8，7』

 第五趟排序后：0，1，2，3，4，『6，5，9，8，7』

 第六趟排序后：0，1，2，3，4，5，『6，9，8，7』

 第七趟排序后：0，1，2，3，4，5，6，『9，8，7』

 第八趟排序后：0，1，2，3，4，5，6，7，『8，9』

 第九趟排序后：0，1，2，3，4，5，6，7，8，『9』

 结果：          『 0，1，2，3，4，5，6，7，8，9 』
————————————————
版权声明：本文为CSDN博主「Alex_McAvoy」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/u011815404/article/details/79256237

堆排序

堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆

算法描述

将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
 

5.归并排序

6.分配排序

箱排序：

箱排序也称桶排序(Bucket Sort)，其基本思想是：设置若干个箱子，依次扫描待排序的记录R[0]，R[1]，…，R[n-1]，把关键字等于k的记录全都装入到第k个箱子里(分配)，然后按序号依次将各非空的箱子首尾连接起来(收集)。

适用于：

关键字取值范围小

基数排序：取多次关键字排序

利用分配和收集两种基本操作。基数排序是一种按记录关键字的各位值逐步进行排序的方法。此种排序一般适用于记录的关键字为整数类型的情况。所有对于字符串和文字排序不适合。

7.内部排序方法比较