排序备忘
摘要
排序是算法的一项基础能力，也是面试必考题。如何写一个恰当的排序，也是一个软件工程师的基本必备技能。
冒泡排序法
冒泡排序法是思想最朴实的排序，通过n^2次交换，将当前最大的，送到序列尾部。
冒泡排序的时间最好，最差，平均时间复杂度都是O(n^2)。好处是稳定，坏处就是真的慢。
private static int[] BubbleSort(int[] input){
int j = 0;
int i = 0;
for(i = 0 ; i < input.length - 1 ;i++){
for(j = 0 ; j < input.length - 1 - i ; j++ ){
if(input[j] > input[j+1]){
int t = input[j];
input[j] = input[j+1];
input[j+1] = t;
}
}
}
return input;
}插入排序
插入排序是将某个元素左边的所有比它大的放到它的右边，直到遇见比它小的为止。这样从左往右排，就可以完成排序。
插入排序的时间最好，最差，平均时间复杂度都是O(n^2)。好处是稳定，坏处是速度也不尽如人意。
private static int[] InsertitonSort(int[] input){
int i = 0 ;
int j = 0 ;
for( i = 1 ; i < input.length ; i++){
int t = input[i];
for( j = i - 1 ; j >= 0 && input[j] > t; j--){
input[j+1] = input[j];
}
input[j+1] = t;
}
return input;
}希尔排序
希尔排序其实是插入排序的变种。只是把每次-1的情况变成了-step。 然后每次step = step/2;
最佳时间复杂度可至O(n^1.3) 最坏情况是O(n^2) 平均时间复杂度不稳定
private static int[] ShellSort(int[] input){
int step = input.length/2;
while(step >= 1){
int i = 0 ;
int j = 0 ;
for( i = 1 ; i < input.length ; i++){
int t = input[i];
for( j = i - step ; j >= 0 && input[j] > t; j-=step){
input[j+step] = input[j];
}
input[j+step] = t;
}
step = step/2;
}
return input;
}快速排序
快排的思想是，选定任一元素。将比它小的排到左边，比它大的排到右边。然后再用上面的思想，对左右进行递归。
在内存有限的情况下，快递是目前最快的排序方法。 其时间复杂度为O(n log n)
private static void QuickSortF(int[] input, int low, int high){
if (low < high){
int pivotIndex = getPovitIndex(input, low ,high);
QuickSortF(input, low , pivotIndex - 1);
QuickSortF(input, pivotIndex+1 , high);
}
}
private static int getPovitIndex(int[] input , int low , int high){
int pivot = input[low];
while(low < high){
while(low < high && input[high] > pivot){
high--;
}
input[low] = input[high];
while(low < high && input[low] <= pivot){
low++;
}
input[high] = input[low];
}
input[low] = pivot;
return low;
}桶排序
当被排序的序列，长度有限，且元素的值的范围有限时，我们可以尝试用空间换时间。
桶排的关键就是将序列的值作为桶的索引。 比如(3,1,4,1)的序列，在桶中的表示就是： (0,2,0,1,1) // 表示有2个1，1个3和1个4。有了这样的桶，自然我们就可以直接生成有序的队列了。
桶排序的时间复杂度与序列最大值与最小值的差有关，假设这个差为M。 同时间复杂度为 O(2*n+M).
private static int[] BucketSort(int[] input){
int max = 0;
for(int i = 0 ; i < input.length ; i++){
if(input[i] < 0){
return null;
}
if(input[i] > max){
max = input[i];
}
}
int[] bucket = new int[max+1];
for(int i = 0 ; i < input.length ; i++){
bucket[input[i]]++;
}
int i = 0;
int j = 0;
while(i<bucket.length){
while(bucket[i]-->0){
input[j] = i;
j++;
}
i++;
}
return input;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2018.10.23 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
