什么是排序
排序的定义
对一序列对象根据某个关键字进行排序（通俗点来说就是吧一堆数据按照从小到大（升序），或者从大到小排列（降序）），我们下面都基于升序来讲解。
排序的相关术语
- 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面
- 不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面
- 内排序：所有排序操作都在内存中完成
- 外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行
- 时间复杂度： 一个算法执行所耗费的时间
- 空间复杂度：运行完一个程序所需内存的大小
排序的分类
算法分析
冒泡排序
冒泡排序（bulleSort）这里就不在多说了，非常经典的一种排序，我们接触的第一种排序啦。
算法描述：
- 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
- 从头到尾两两元素进行比较交换 ，这时尾部元素为最大元素
- 针对所有的元素重复以上的步骤，除了最后一个
- 重复步骤1~3，直到排序完成
算法分析
时间复杂度：
- 当数据有序时 最好 O(n)
- 当数据无序时 最差 O(n2)
空间复杂度O(1)
不稳定
实现代码
java"> public static void bullSort(int[] array){
for(int i=0;i<array.length;i++)
{
int flag=0;
for(int j=0;j<array.length-1-i;j++)
{
if(array[j]>array[j+1])
{
int tmp=array[j];
array[j]=array[j+1];
array[j+1]=tmp;
flag=1;
}
}
if(flag==0)
{
break;
}
}
}
选择排序
选择排序(selectSort)是一种简单直观的排序算法。首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
算法描述
- 先将第一个元素开始，将第一个元素与后面的每一个元素进行比较，如果比其小，则进行交换，直到数组遍历完，第一个元素便是最小的元素
- 接着从第二个元素开始，与第二个元素之后的元素进行比较
- 重复上述过程
算法分析
时间复杂度：
- 当数据有序时 最好 O(n)
- 当数据无序时 最差 O(n2)
空间复杂度O(1)
稳定
实现代码
java"> public static void selectSort(int[] array) {
for(int i=0;i<array.length-1;i++)
{
for(int j=i+1;j<array.length;j++)
{
if(array[j]<array[i])
{
int tmp=array[i];
array[i]=array[j];
array[j]=tmp;
}
}
}
}
希尔排序
希尔排序（shellSort）也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，它与插入排序的不同之处在于，它会优先比较距离较远的元素（将小的数据尽可能的放到前面）希尔排序是把数据按照增量数组中得值分成好多个组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的数据越来越多，当增量减至1时，整个数据恰被分成一组，其实此时也就是插入排序了。（增量数组当中的值为素数，但最后一个是1）
算法描述
- 选择一个增量序列drr[]
- 从增量序列中取出第一个k，对序列进行分组，并对进行每组进行插入排序
- 选择增量序列中的下一个，重复2步骤
- 最好 O（n1.5）
- 最坏 O（n2）
空间复杂度O（1）
不稳定
实现代码
java"> public static void shellSort(int[] array) {
int[] drr = {5,3,1};//增量数组
for (int i = 0; i < drr.length; i++) {
shell(array,drr[i]);
}
}
public static void shell(int[] array ,int gap) {
int j,tmp;
for(int i=gap;i<array.length;i++)
{
tmp=array[i];
j=i-gap;
for(;j>=0;j-=gap)
{
if(array[j]>tmp)
{
array[j+gap]=array[j];
}else{
break;
}
}
array[j+gap]=tmp;
}
}
举例数组为[12,5,9,16,6,8,27,58,80,0,7,4,33,55,77]
增量序列为[5,3,1]
- 分五组
- 每组进行插入排序
- 在分三组，在进行插入排序
归并排序
归并排序（mergeSort）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。（原理-合并两个有序数组）
算法描述
来分析一下吧，对于归并算法，有两个部分组成，分解和合并。首先讲讲分解，我们需要将待排序的序列不停地进行分解，通过两个索引变量控制，一个初始索引（low），一个结尾索引（high）。只有当两索引重合才结束分解。接下来是合并，合并操作也是最麻烦的，也是通过两个索引变量s1,s2。开始s1在左边序列的第一个位置，s2在右边序列的第一个位置，然后就是寻找左右两个序列中的最小值(合并两个数组)，放到新序列中，这时可能会出现一边的元素都放置完毕了，而另外一边还存在元素，此时只需将剩余的元素按顺序放进新序列即可，因为这时左右两边的序列已经是有序的了，最后将新序列复制到旧序列。这里也特别需要注意，因为合并的过程是分步的，而并非一次合并完成，所以数组的索引是在不断变化的。(所以需要加strat保证位置的正确性)
算法分析
时间复杂度：
- 最好：O(nlogn)
- 最坏：O(nlogn)
空间复杂度 O（n）
稳定
实现代码
- 递归实现
java"> public static void mergeSort(int[] array){
mergeSortInternal(array,0,array.length-1);
}
public static void mergeSortInternal(int[] array,int low,int high){
if(low>=high) return ;
int mid=(low+high)/2;
//分解
mergeSortInternal(array,low,mid);
mergeSortInternal(array,mid+1,high);
//合并
merge(array,low,mid,high);
}
//核心：两数组进行合并
public static void merge(int[] array,int start,int mid,int end){
int s1=start;
int s2=mid+1;
int[] tmp=new int[end-start+1];
int k=0;
while(s1<=mid&&s2<=end)
{
if(array[s1]<=array[s2])
{
tmp[k++]=array[s1++];
}else{
tmp[k++]=array[s2++];
}
}
//有可能第一个段还有数据 有可能第2个段也有数据
while(s1<=mid)
{
tmp[k++]=array[s1++];
}
while(s2<=end)
{
tmp[k++]=array[s2++];
}
for(int i=0;i<end-start+1;i++)
{
//一定要加上start
array[i+start]=tmp[i];
}
}
// 归并排序
private static void merge_sort(int[] arr, int low, int high) {
if (low>=high) return;
int mid = low+high>>1;
merge_sort(arr, low, mid);
merge_sort(arr, mid + 1, high);
int[] tmp = new int[high - low + 1];
int i = low, j = mid + 1, k = 0;
// 进行归并
while (i <= mid && j <= high) {
if (arr[i] <= arr[j])
tmp[k++] = arr[i++];
else
tmp[k++] = arr[j++];
}
while (i <= mid) tmp[k++] = arr[i++];
while (j <= high) tmp[k++] = arr[j++];
// 进行赋值
for (i = low, j = 0; i <=high; i++, j++)
arr[i] = tmp[j];
}
- 非递归实现
java"> //非递归版本
public static void mergeSort2(int[] array) {
for (int i = 1; i < array.length; i*=2) {
merge(array,i);
}
}
public static void merge(int[] array,int gap) {
int s1 = 0;
int e1 = s1+gap-1;
int s2 = e1+1;
int e2 = s2+gap-1 < array.length ? s2+gap-1 : array.length-1;
int[] tmp = new int[array.length];
int k = 0;//下标
//当有两个归并段的时候
while (s2 < array.length) {
//当当有两个归并段 且 这两个段内都要数据
while (s1 <= e1 && s2<= e2) {
if(array[s1] <= array[s2]) {
tmp[k++] = array[s1++];
}else{
tmp[k++] = array[s2++];
}
}
while (s1 <= e1) {
tmp[k++] = array[s1++];
}
while (s2 <= e2){
tmp[k++] = array[s2++];
}
//从这里开始的时候，每个下标都可能越界
s1 = e2+1;
e1 = s1+gap-1;
s2 = e1+1;
e2 = s2+gap-1 < array.length ? s2+gap-1 : array.length-1;
}
//退出上面循环后，
// 那么把s1段内的数据给拷贝下来,因为 有可能e1已经越界了
while (s1 < array.length) {
tmp[k++] = array[s1++];
}
//拷贝tmp到原数组当中
for (int i = 0; i < tmp.length; i++) {
array[i] = tmp[i];
}
}
直接插入排序
直接插入排序（insertSort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
生活中打扑克牌就是插入排序的体现
算法描述
- 1.从第一个元素开始，该元素可以认为已经被排序；
- 2.取出下一个元素，在已经排序的元素序列中从后向前扫描；
- 3.如果该元素（已排序）大于新元素，将该元素移到下一位置；
- 4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置，然后将新元素插入到该位置后；
- 5.重复步骤2~4。
算法分析
时间复杂度：
- 当数据有序时 最好：O(n)
- 数据是无序的 最坏：O(n2)
空间复杂度 O（1）
稳定
实现代码
java"> public class insertSort {
public static void insertSort(int[] array) {
for (int i = 1; i < array.length; i++) {
int tmp = array[i];
int j = i-1;
for (j; j >= 0 ; j--) {
//如果这里是一个大于等于号 此时这个排序就不稳定了
if(array[j] > tmp) {
array[j+1] = array[j];
}else {
break;
}
}
array[j+1] = tmp;
}
}
直接插入排序数据越有序，排序越快。当数据大部分有序时，使用直接插入排序最合适，直接插入排序也会用在其他一些排序的优化上。
快速排序（快排）
快速排序（quickSort）的基本思想：通过一趟排序将待排记录分成两部分，其中一部分数据比某一个值均大，另一部分比这个值均小，（称这个值为基准pivot）然后分别对这两部分记录继续进行排序，以达到整个序列有序。
算法描述
- 从数列中挑出一个元素，称为 “基准”（pivot）
- 在找的过程中，重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）
- 递归地（quick）把小于基准值元素和大于基准值元素在进行排列即可
算法分析
时间复杂度：
- 最好：O(nlogn)
- 数据是有序的 最坏：O(n2)
空间复杂度 O（nlogn）
不稳定
实现代码
- 递归实现
java"> //递归写法及其优化
public static void quickSort1(int[] array){
quick(array,0,array.length-1);
}
//找基准
public static int pivot(int[] array,int low,int high) {
int tmp = array[low];
while (low < high) {
while (array[high]>=tmp&&low<high) {
high--;
}
//把high数据赋值给low
array[low]=array[high];
while (array[low]<=tmp&&low<high) {
low++;
}
//把low下标的值给high
array[high]=array[low];
}
array[low] = tmp;
return low;
}
public static void insertSort(int[] array,int low,int high)
{
int tmp,j;
for(int i=low;i<=high;i++)
{
tmp=array[i];
j=i-1;
for(;j>=low;j--)
{
if(array[j]>tmp)
{
array[j+1]=array[j];
}else{
break;
}
}
array[j+1]=tmp;
}
}
public static void quick(int[] array,int low,int high){
if(low>=high) return ;
if(high-low + 1 <= 50) {
//使用插入排序
insertSort(array,low,high);
return;//记着这里一定要return 这里说明 这个区别范围有序了 直接结束
}
//优化1
medianOfThree(array,low,high);
int piv=pivot(array,low,high);
quick(array,low,piv-1);
quick(array,piv+1,high);
}
//三数取中法优化（找基准）
public static void swap(int[] array,int i,int j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
public static void medianOfThree(int[] array,int low,int high) {
int mid = (low+high)/2;
//array[mid] <= array[low] <= array[high]
if(array[low] < array[mid]) {
swap(array,low,mid);
}//array[mid] <= array[low]
if(array[low] > array[high]) {
swap(array,low,high);
}//array[low] <= array[high]
if(array[mid] > array[high]) {
swap(array,mid,high);
}//array[mid] <= array[high]
}
//2 递归实现
private static void quickSort(int[] arr, int low, int high) {
if(low>=high) return ;
int i=low,j=high;
while (i< j) {
while (i < j && arr[j] >= arr[low]) j--;
while (i < j && arr[i] <= arr[low]) i++;
swap(arr, i, j);
}
swap(arr, i, low);
quickSort(arr, low, i - 1);
quickSort(arr, i + 1, high);
}
private static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
- 非递归代码
java">//非递归写法
//找基准
public static int pivot(int[] array,int low,int high) {
int tmp = array[low];
while (low < high) {
while (array[high]>=tmp&&low<high) {
high--;
}
//把high数据赋值给low
array[low]=array[high];
while (array[low]<=tmp&&low<high) {
low++;
}
//把low下标的值给high
array[high]=array[low];
}
array[low] = tmp;
return low;
}
public static void quickSort2(int[] array) {
Stack<Integer> stack = new Stack<>();
int low = 0;
int high = array.length-1;
int piv = pivot(array,low,high);//
if(piv > low + 1) {
stack.push(low);
stack.push(piv-1);
}
if(piv < high-1) {
stack.push(piv+1);
stack.push(high);
}
while (!stack.empty()) {
high = stack.pop();
low = stack.pop();
piv = pivot(array,low,high);
if(piv > low + 1) {
stack.push(low);
stack.push(piv-1);
}
if(piv < high-1) {
stack.push(piv+1);
stack.push(high);
}
}
}
堆排序
堆排序（heapSort）在学堆排序之前我们需要了解大根堆、小根堆、如何构造堆等相关的一些知识（不了解的话，可以看看博主之前写的堆的文章）。
算法描述
我们默认是升序从小到大，我们分为三个步骤
- 我们需要建一个大堆（降序的话建小堆）
- 然后将第一个元素（最大的元素）与最后一个元素进行交换，然后再对第一个元素进行向下调整（保证剩余元素为大根堆，第一个元素为剩下元素的最大值）
- 然后再将倒数第二个元素与第一个元素进行2过程，重复进行，知道走到第一个元素结束
算法分析
时间复杂度：
- 最好的最坏都是O（n*log2n）
空间复杂度O（1）
稳定的
实现代码
代码
java"> //向下调整
public static void adjustDown(int[] array,int parent,int len) {
int child = 2*parent+1;
while (child < len) {
if(child+1 < len && array[child] < array[child+1]) {
child++;//
}
if(array[child] > array[parent]) {
int tmp = array[child];
array[child] = array[parent];
array[parent] = tmp;
parent = child;
child = 2*parent+1;
}else {
break;
}
}
}
//建大堆
public static void crateBigHeap(int[] array) {
for(int i = (array.length-1-1) /2; i>= 0;i--) {
adjustDown(array,i,array.length);
}
}
//堆排序
public static void heapSort(int[] array) {
crateBigHeap(array);
int end=array.length-1;
while(end>0)
{
int tmp=array[0];
array[0]=array[end];
array[end]=tmp;
adjustDown(array,0,end);
end--;
}
}
海量数据的排序问题
外部排序：排序过程需要在磁盘等外部存储进行的排序前提：内存只有 1G，需要排序的数据有 100G
因为内存中因为无法把所有数据全部放下，所以需要外部排序，而归并排序是最常用的外部排序
- 先把文件切分成 200 份，每个 512 M
- 分别对 512 M 排序，因为内存已经可以放的下，所以任意排序方式都可以
- 进行 200 路归并，同时对 200 份有序文件做归并过程，最终结果就有序了
总结
- 只有冒泡插入归并是稳定的，其余是不稳定的
- 归并、快排和堆比较难，一定要理解，他们三个也挺像的，时间复杂度都是O（nlogn），如果数据无序的话快排最快（不然为啥叫快排哈哈哈！）但空间的复杂度不同，归并最大是O（n）（因为开辟了数组），其次是快排为O（logn）（因为递归中开辟了栈帧），最小是堆排为O(1)。大家要理解。
- 只有归并是外排序，其余都是内排序
上面这些排序都是基于比较然后进行交换的思想，但也有不需要交换的方法，那便是计数排序、桶排序等等，大家感兴趣的话可以下去看看，这里就不做过多描述了。
好了，如果有错误和不懂的地方的话留言评论即可。
