排序的相关概念

排序：所谓排序，就是使一串记录，按照其中的某个或某几个关键字的大小，递增或递减排列起来的操作。

稳定性：在待排序的记录序列中，存在多个具有相同关键字的记录，若经过排序，这些记录的相对次序保持不变，则称这种排序算法是稳定的。

内部排序：把数据全部加载到内存中进行排序。

外部排序：数据太多，内存不能存储了，将数据放到磁盘、U盘上进行排序。

排序算法的分类

插入排序：直接插入排序、希尔排序

选择排序：选择排序、堆排序

交换排序：冒泡排序、快速排序

归并排序：归并排序

排序算法实现

1.归并排序

基本思想：先将元素序列进行分解，以(0+arr.length-1)/2为分界点，将序列分为0~(0+arr.length-1)/2,(0+arr.length-1)/2+1~arr.length-1；以此类推，直到每个元素序列只有一个元素。依次将两个元素序列进行有序合并，合并为一个有序表，称为二路归并。

代码实现：

//归并排序 递归public static void mergeSort(int[] arr){mergeSortFunc(arr,0,arr.length-1);}private static void mergeSortFunc(int[] arr,int left,int right){if (left>=right){return;}int mid = (left+right)/2;mergeSortFunc(arr,left,mid);mergeSortFunc(arr,mid+1,right);merge(arr,left,right,mid);}private static void merge(int[] arr,int start,int end,int mid){int s1= start;int s2=mid+1;int[] tmp = new int[end-start+1];//tmp数组下标int k=0;while(s1<=mid && s2<=end){if (arr[s1]<=arr[s2]){tmp[k++]=arr[s1++];}else {tmp[k++]=arr[s2++];}}while (s1<=mid){tmp[k++]=arr[s1++];}while (s2<=end){tmp[k++]=arr[s2++];}for (int i = 0; i < tmp.length; i++) {arr[i+start]=tmp[i];}}

非递归 归并排序

//非递归 归并排序public static void mergeSort1(int[] arr){int gap=1;while (gap<arr.length){for (int i = 0; i < arr.length; i += gap*2) {int left=i;int mid = left+gap-1;if (mid>=arr.length){mid=arr.length-1;}int right=mid+gap;if (right>=arr.length){right=arr.length-1;}merge(arr,left,right,mid);}gap *=2;}}private static void merge(int[] arr,int start,int end,int mid){int s1= start;int s2=mid+1;int[] tmp = new int[end-start+1];//tmp数组下标int k=0;while(s1<=mid && s2<=end){if (arr[s1]<=arr[s2]){tmp[k++]=arr[s1++];}else {tmp[k++]=arr[s2++];}}while (s1<=mid){tmp[k++]=arr[s1++];}while (s2<=end){tmp[k++]=arr[s2++];}for (int i = 0; i < tmp.length; i++) {arr[i+start]=tmp[i];}}

性能总结：

1.归并排序思考的更多的是解决在磁盘中的外排序问题。

2.时间复杂度：O(N*logN)

3.空间复杂度：O(N)

4.稳定性：稳定