排序
排序
http://www.nowcoder.com/questionTerminal/2baf799ea0594abd974d37139de27896
排序
冒泡排序(稳定排序)
思想：冒泡排序的思想就是比较当前数和后一个数的大小，将较大的数往后移动，这样可以确保一轮下来能将最大的数放在数组的最末端。然后重复此操作即可完成排序。
上面第一轮比较完，我们可以看到最大的数5已经被放在了最端，此时我们只需要将去掉最大的数的那部分（2，3，1，4）进行重复的操作。
public int[] MaopaoSort (int[] arr) {
if (arr.length < 2)
return arr;
for (int i = 0; i < arr.length-1; i++) {
for (int j = 0; j < arr.length-i-1; j++) {
if (arr[j] > arr[j+1])
swap(arr,j,j+1);
}
}
return arr;
} 时间复杂度
若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数M 均达到最小值：
Cmin = n-1 ， Mmin = 0
所以，冒泡排序最好的时间复杂度为 O(n)
若初始文件是反序的，需要进行 n-1趟排序。每趟排序要进行 n-1 次关键字的比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：
Cmax = n(n-1)/2 = O(n2) Mmax = 3n(n-1)/2 = O(n2)
冒泡排序的最坏时间复杂度为O(n2)
综上，因此冒泡排序总的平均时间复杂度为O(n2)
快速排序
快速排序(Quick Sort)：快速排序用到了分治思想，同样的还有归并排序。乍看起来快速排序和归并排序非常相似，都是将问题变小，先排序子串，最后合并。快速排序又是对冒泡排序的一种改进方法，在冒泡排序中，进行元素的比较和交换是在相邻元素之间进行的，元素每次交换只能移动一个位置，所以比较次数和移动次数较多，效率相对较低。而在快速排序中，元素的比较和交换是从两端向中间进行的，较大的元素一轮就能够交换到后面的位置，而较小的元素一轮就能交换到前面的位置，元素每次移动的距离较远，所以比较次数和移动次数较少，速度较快，故称为“快速排序”。
快速排序的基本思想是：
- 在待排序的元素任取一个元素作为基准(通常选第一个元素，但最优的选择方法是从待排序元素中随机选取一个作为基准)，称为基准元素；
- 将待排序的元素进行分区，比基准元素大的元素放在它的右边，比其小的放在它的左边；
- 对左右两个分区重复以上步骤直到所有元素都是有序的
/**
* 快速排序
* @param arr
* @param left
* @param right
* @return
*/
public int[] quickSort(int[] arr, int left, int right){
if (left < right){
int point = partition(arr,left,right);
quickSort(arr,left,point-1);
quickSort(arr,point+1,right);
}
return arr;
}
/**
* 快速排序 找出分割点
* @param arr
* @param left
* @param right
* @return
*/
private int partition(int[] arr, int left, int right) {
//将第一个数作为基准比较值
int base = arr[left];
while(left < right){
while (left < right && arr[right] >= base)
right--;
swap(arr,left,right);
while(left < right && arr[left] <= base)
left++;
swap(arr,left,right);
}
return left;
} 可以看到上面的图，是一种最坏的情况，此时分割数组的时候，最左边的数组只比原来的数组小一个元素，而最右边的数组只有一个元素，要是一直是这种情况下，那么快速排序算法的时间复杂度退化成了O(n2)；
最好的情况下，是分割的最优数组长度相等。时间复杂度为 O(nlog2N)
优化（随机基准数）
/**
* 快速排序 找出分割点
* @param arr
* @param left
* @param right
* @return
*/
private int partition(int[] arr, int left, int right) {
/*添加随机寻找基准值*/
int random_index = new Random().nextInt(right-left+1)+left;
System.out.println("随机值"+random_index);
swap(arr,left,random_index);
//将第一个数作为基准比较值
int base = arr[left];
while(left < right){
while (left < right && arr[right] >= base)
right--;
swap(arr,left,right);
while(left < right && arr[left] <= base)
left++;
swap(arr,left,right);
}
return left;
} 归并排序
归并排序（Merge Sort）是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
归并排序是稳定排序，它也是一种十分高效的排序，能利用完全二叉树特性的排序一般性能都不会太差。java中Arrays.sort()采用了一种名为TimSort的排序算法，就是归并排序的优化版本。从上文的图中可看出，每次合并操作的平均时间复杂度为O(n)，而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且，归并排序的最好，最坏，平均时间复杂度均为O(nlogn)。
/**
* 归并排序
* @param arr
* @param left
* @param right
* @param tmp
*/
public void mergeSort(int[] arr, int left, int right, int[] tmp){
if (left == right)
return;
int mid = left+((right-left)>>1);
mergeSort(arr,left,mid, tmp);
mergeSort(arr,mid+1,right, tmp);
merge(arr,left,mid,right,tmp);
}
/**
* 向上合并
* @param arr
* @param left
* @param mid
* @param right
* @param tmp
*/
private void merge(int[] arr, int left, int mid, int right, int[] tmp) {
int i = left;
int l = left; //左半数组的下标
int m = mid+1; //右半数组的下标
//合并放在辅助数组中
while (l <= mid && m <= right)
tmp[i++] = arr[l]<arr[m]?arr[l++]:arr[m++];
while (l <= mid)
tmp[i++] = arr[l++];
while(m <= right)
tmp[i++] = arr[m++];
//将辅助数组中的元素复制到原数组中
for (int j = left; j <= right; j++) {
arr[j] = tmp[j];
}
} 归并排序比较占用内存，但却是一种效率高且稳定的算法。
改进归并排序在归并时先判断前段序列的最大值与后段序列最小值的关系再确定是否进行复制比较。如果前段序列的最大值小于等于后段序列最小值，则说明序列可以直接形成一段有序序列不需要再归并，反之则需要。所以在序列本身有序的情况下时间复杂度可以降至O(n)
TimSort可以说是归并排序的终极优化版本，主要思想就是检测序列中的天然有序子段（若检测到严格降序子段则翻转序列为升序子段）。在最好情况下无论升序还是降序都可以使时间复杂度降至为O(n)，具有很强的自适应性。
| 最好时间复杂度 | 最坏时间复杂度 | 平均时间复杂度 | 空间复杂度 | 稳定性 | |
|---|---|---|---|---|---|
| 传统归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | T(n) | 稳定 |
| 改进归并排序 [1] | O(n) | O(nlogn) | O(nlogn) | T(n) | 稳定 |
| TimSort | O(n) | O(nlogn) | O(nlogn) | T(n) | 稳定 |
堆排序HeapSort
public int[] heapSort(int[] arr){
//构建堆
for (int i = 0; i < arr.length; i++) {
creatSort(arr,i);
}
//最后一个元素跟大根堆顶交换
int size = arr.length;
swap(arr,0,--size);
while(size > 0){
heapify(arr,0,size);
swap(arr,0,--size);
}
return arr;
}
/**
* 创建大根堆
* @param arr
* @param index
*/
public void creatSort(int[] arr,int index){
while(arr[index] > arr[(index-1)/2]){
swap(arr,index,(index-1)/2);
index = (index-1)/2;
}
}
/**
* 大根堆顶变小，重新调整堆，向下调整
* @param arr
* @param index
* @param size
*/
public void heapify(int[] arr,int index,int size){
int left = index*2+1;
while(left < size){
//比较index的左右节点的大小，取大的
int large = left+1 < size && arr[left] < arr[left+1]?left+1:left;
large = arr[large] > arr[index]? large:index;
//如果下标还是原来的根的下标，就结束调整
if (large == index)
break;
swap(arr,index,large);
index = large;
left = index*2+1;
}
} 优先队列PriorityQueue
优先队列不再遵循先入先出的原则，而是分为两种情况：
- 最大优先队列，无论入队顺序，当前最大的元素优先出队；
- 最小优先队列，无论入队顺序，当前最小的元素优先出队；
/**
* 利用优先队列排序
* @param arr
* @return
*/
public int[] PriorityQueueSort(int[] arr){
PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1.compareTo(o2);
}
});
for (int i = 0; i < arr.length; i++) {
queue.add(arr[i]);
}
int[] newarr = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
newarr[i] = queue.poll();
}
return newarr;
} Java内部sort排序使用的排序算法
元素个数 < 47 : 插入排序
47 <= 元素个数 < 286 : 快速排序
元素个数 > 286 ：归并排序
查看10道真题和解析
