排序基本概念
什么是排序
排序（sorting）的功能是将一个数据元素的任意序列，重写排列成一个按关键字有序的序列。
内部排序和外部排序
一类是整个排序过程在内存储器中进行，成为内部排序
另一类是由于待排序元素数量太大，以至于内存储器无法容纳全部数据，排序需要借助外部存储设备才能完成，这类排序成为外部排序。
稳定排序和就地排序
稳定排序：假设在待排序的文件中，存在两个或两个以上的记录具有相同的关键字，在用某种排序法排序后，若这些相同关键字的元素的相对次序仍然不变，则这种排序方法是稳定的。
其中冒泡，插入，基数，归并属于稳定排序，选择，快速，希尔，归属于不稳定排序。
就地排序：若排序算法所需的辅助空间并不依赖于问题的规模n，即辅助空间为O（1），则称为就地排序。
比较排序和非比较排序
大部分排序都是需要通过比较首先来判断大小，作为排序的依据的。
但是也有例外的，比如计数排序、基数排序，不需要进行比较。
排序类型 ![]()
常见排序算法
排序效率
时间复杂度最高的就是三种基本排序：直接插入、简单选择、冒泡排序。
快速排序
冒泡排序的改进版，也是最好的一种内排序，还涉及到分治和递归。
是由C. A. R. Hoare在1962年提出的一种划分交换排序，它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。
它的基本思想是：
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，
然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
一趟快速排序的算法是：
1）设置两个变量i、j，排序开始的时候：i=0，j=N-1;
2）以第一个数组元素作为关键数据，赋值给key，即key=A[0];
3）从j开始向前搜索，即由后开始向前搜索（j--），找到第一个小于key的值A[j]，将值为key的项与A[j]交换;
4）从i开始向后搜索，即由前开始向后搜索（i++），找到第一个大于key的A[i]，将值为key的项与A[i]交换;
5）重复第3、4步，直到i=j; （3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[j]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。
public static void quickSort(int[] arr) {
int low = 0;
int high = arr.length-1;
quickSort(arr,low,high);
}
private static void quickSort(int[] arr,int low, int high) {
if(low < high) {
// 分区操作，将一个数组分成两个分区，返回分区界限索引
int index = partition(arr,low,high);
// 对左分区进行快排
quickSort(arr,low,index-1);
// 对右分区进行快排
quickSort(arr,index+1,high);
}
}
private static int partition(int[] arr,int low,int high) {
// 指定左指针i和右指针j
int i = low;
int j = high;
// 将第一个数作为基准值
int x = arr[low];
// 使用循环实现分区操作
while(i < j) {
// 1.从右向左移动j，找到第一个小于基准值的值
while(arr[j] >= x && i < j) {
j--;
}
// 2.将右侧找到小于基准数的值加入到左边的位置，左指针向中间移动一个位置i++
if( i < j) {
arr[i] = arr[j];
i++;
}
// 3.从左向右移动i，找到第一个大于等于基准值的值 arr[i]
while(arr[i] < x && i < j) {
i ++;
}
// 4.将左侧找到的大于等于基准的值加入到右边，右指针向中间移动一个位置 j--
if(i < j) {
arr[j] = arr[i];
j --;
}
}
// 使用基准值，这就是基准值的最终位置
arr[i] = x;
// 返回基准值的位置索引
return i;
}
京公网安备 11010502036488号