排序篇
概述
参考https://www.zybuluo.com/MicroCai/note/77440 http://www.jianshu.com/p/ae97c3ceea8d
用到的数据结构都是数组(array)
稳定排序
稳定排序是指：若是数组中有相同的元素，则相同的元素的相对位置不变。
| 排序名称 | 最好 | 最坏 | 平均时间复杂度 | 空间复杂度 | 备注 |
|---|---|---|---|---|---|
| 冒泡(Bubble Sort) | O(n) | O(n²) | O(n²) | O(1) | |
| 插入（Insertion Sort） | O(n) | O(n²) | O(n²) | O(1) | |
| 桶排序(Bucket Sort) | O(n+k) | O(n²) | O(n+k) | O(nk) | 最快 |
| 计数排序（Counting Sort) | O(n+k) | O(n+k) | O(n+k) | ||
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | |
| 二叉排序树 | O(n²) | O(nlogn) | O(n) | ||
| 基数排序(Radix Sort) | O(nK) | O(nK) | O(nK) | O(n+k) |
不稳定排序
| 排序名称 | 最好 | 最坏 | 平均时间复杂度 | 空间复杂度 | 备注 |
|---|---|---|---|---|---|
| 选择排序(Selection Sort) | O(n²) | O(n²) | O(n²) | O(1) | |
| 希尔排序(Shell Sort) | O(n) | O(n²) | O(n^1.5) | O(1) | |
| 堆排序(Heap Sort) | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | |
| 快速排序(Quicksort) | O(nlogn) | O(n²) | O(nlogn) | O(n) |
前言
注意：本案例中实现的都是从小到大的排序，请注意从大到小的排序
主函数:
public static void main(String[] args) {
int[] a={34,21,5,2,3,12,56,13,37,22};
BubbleSort(a);
for(int one:a){
System.out.print(one+" ");
}
}
1. 冒泡排序
1. 基本思想：两个数比较大小，较大的数下沉，较小的数冒起来。
2. 过程：第一趟，从后向前遍历n-1个元素，比较所有相邻元素，将最小的元素交换到数组最前面。第二趟，从后向前遍历n-2个元素，比较所有相邻元素，将第二小的元素交换到数组第2的位置
3. 算法样例
4. 代码实现：
public static void BubbleSort(int[]arr){
int temp;
int len=arr.length;
for(int i=0;i<len-1;i++)第i趟，一共length-1趟
for(int j=len-1;j>i;j--)//从后向前遍历，比较相邻的两个元素
if(arr[j]<arr[j-1]){//相邻的元素后面的元素比前面的小，则交换位置，将小的元素向前交换
temp=arr[j];
arr[j]=arr[j-1];
arr[j-1]=temp;
}
}
5. 复杂度
最好：O(n)
最坏：O(n²)
平均：O(n²)
6. 优化
设置标志位flag，如果发生了交换flag设置为true；如果没有交换就设置为false。
这样当一轮比较结束后如果flag仍为false，即：这一轮没有发生交换，说明数据的顺序已经排好，没有必要继续进行下去。
public static void BubbleSort(int[]arr){
int temp;
int len=arr.length;
boolean flag;//标志位
for(int i=0;i<len;i++){
flag=false;
for(int j=len-1;j>i;j--)
if(arr[j]<arr[j-1]){
temp=arr[j];
arr[j]=arr[j-1];
arr[j-1]=temp;
flag=true;
}
if(!flag) break;
}
}
2. 选择排序
1. 基本思想
在长度为N的无序数组中，第一次遍历n-1个数，找到最小的数值与第一个元素交换；
第二次遍历n-2个数，找到最小的数值与第二个元素交换； ......
第n-1次遍历，找到最小的数值与第n-1个元素交换，排序完成。
2.算法过程
3. 代码实现
public static void select_sort(int []arr){
int len=arr.length;
int temp;
for(int i=0;i<len;i++){
int k=i;
for(int j=i+1;j<len;j++){//遍历i之后的元素，找到一个最小的与i上的元素交换
if(arr[j]<arr[k]){
k=j;
}
}
if(k!=i){//交换
temp=arr[i];
arr[i]=arr[k];
arr[k]=temp;
}
}
}
4. 复杂度
最好：O(n²)
最坏：O(n²)
平均：O(n²)
3. 插入排序
1. 基本思想
在要排序的一组数中，假定前n-1个数已经排好序，现在将第n个数插到前面的有序数列中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。
2.算法过程
3.代码实现
public static void insert_sort(int arr[]){
int temp;
int len=arr.length;
for(int i=0;i<len-1;i++)//0~len-1;
for(int j=i+1;j>0;j--){//将i+1的元素与之前的元素比较
if(arr[j]<arr[j-1]){
temp=arr[j];
arr[j]=arr[j-1];
arr[j-1]=temp;
}
else//不需要交换
break;
}
}
复杂度
最好：O(n)
最坏：O(n²)
平均：O(n²)
4. 希尔排序
http://blog.csdn.net/morewindows/article/details/6668714 1. 基本思想 分组插入排序 根据某一增量分为若干组，对每组插入排序 然后逐渐增量减小，重复。直至增量为1，此时数据数列基本有序，最后进行插入排序。
2.实例讲解
3.代码实现
public static void shell_sort(int arr[]){
int len=arr.length;
int gap;
for(gap=len/2;gap>0;gap/=2)//步长，划分几组序列（每组序列中元素以步长为间隔）
for(int i=0;i<gap;i++){//遍历每个组
for(int j=i+gap;j<len;j+=gap)//遍历每组序列中的元素
if(arr[j]<arr[j-gap])//若新的元素temp比前面的元素小，则执行插入排序
{
int temp=arr[j];
int k=j-gap;
while(k>=0&&arr[k]>temp){//找到新的元素要插入的位置
arr[k+gap]=arr[k];//元素后移
k-=gap;
}
arr[k+gap]=temp;
}
}
}
很明显，上面的shellsort1代码虽然对直观的理解希尔排序有帮助，但代码量太大了，不够简洁清晰。因此进行下改进和优化，以第二次排序为例，原来是每次从1A到1E，从2A到2E，可以改成从1B开始，先和1A比较，然后取2B与2A比较，再取1C与前面自己组内的数据比较…….。这种每次从数组第gap个元素开始，每个元素与自己组内的数据进行直接插入排序显然也是正确的。
进一步精简
public static void shell_sort(int arr[]){
int gap;
int len=arr.length;
for(gap=len/2;gap>0;gap/=2)
for(int j=gap;j<len;j++)//从第gap元素开始遍历
if(arr[j]<arr[j-gap]){//每个元素与自己组内的数据进行直接插入排序（相隔一个gap的都是一个组内的）
int temp=arr[j];
int k=j-gap;
while(k>=0&&arr[k]>temp){//寻找插入位置
arr[k+gap]=arr[k];//元素后移
k-=gap;
}
arr[k+gap]=temp;
}
}
5.快速排序
1.基本思想
分治
- 先从数列中取出一个数作为key值；
- 将比这个数小的数全部放在它的左边，大于或等于它的数全部放在它的右边；
2.实例解析
数组：72 6 57 88 60 42 83 73 48 85
0 1 2 3 4 5 6 7 8 9
选数组第一个数为key
则：
初始时：i=0；j=9；key=72
第一次划分后：
数组：48 6 57 72 60 42 83 73 88 85
0 1 2 3 4 5 6 7 8 9
3.代码实现
public static void quickSort(int arr[],int l,int r){
if(l>=r)
return;
int i=l;
int j=r;
int key=arr[l];//选择第一个数为key
while(i<j){
while(i<j&&arr[j]>=key){//从右向左找第一个小于key的值，为j
j--;
}
if(i<j){
arr[i]=arr[j];//将第一个位置上赋值为j上的值
i++;
}
while(i<j&&arr[i]<key){//从左向右找第一个大于key的值，为i
i++;
}
if(i<j){
arr[j]=arr[i];//将原来j上的位置赋值为i上的值;
j--;
}
}
arr[i]=key;
quickSort(arr,l,i-1);
quickSort(arr,i+1,r);
}
或：
public class MySort{
static void quicksort(int n[], int left, int right) {
int dp;
if (left < right) {
dp = partition(n, left, right);
quicksort(n, left, dp - 1);
quicksort(n, dp + 1, right);
}
}
static int partition(int n[], int left, int right) {
int pivot = n[left];
while (left < right) {
while (left < right && n[right] >= pivot)
right--;
if (left < right)
n[left++] = n[right];
while (left < right && n[left] <= pivot)
left++;
if (left < right)
n[right--] = n[left];
}
n[left] = pivot;
return left;
}
public static void main(String ...strings){
int[] a={34,21,5,2,3,3,12,12,56,13,37,22};
quicksort(a,0,a.length-1);
for(int one:a){
System.out.print(one+" ");
}
}
}
/*输出：
2 3 3 5 12 12 13 21 22 34 37 56
*/
6.归并排序
1.基本思想
分治
首先考虑下如何将2个有序数列合并。这个非常简单，只要从比较2个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。
2.代码实现
//temp是辅助数组，最开始初始化int temp[]=new int[a.length]
public static void merge_sort(int a[],int l,int r,int temp[]){
if(l<r){
int m=(l+r)/2;
merge_sort(a,l,m,temp);//左半部分排好序
merge_sort(a,m+1,r,temp);//右半部分排好序
mergeArray(a,l,m,r,temp);//合并
}
}
//合并已排好序的arr[left...middle]和arr[middle+1....right]。
public static void mergeArray(int a[],int left,int middle,int right,int temp[]){
int i=left;
int m=middle;
int j=middle+1;
int n=right;
int k=0;
while(i<=m && j<=n){
if(a[i] <= a[j]){
temp[k] = a[i];
k++;
i++;
}else{
temp[k] = a[j];
k++;
j++;
}
}
while(i<=m){
temp[k] = a[i];
k++;
i++;
}
while(j<=n){
temp[k] = a[j];
k++;
j++;
}
//把数据复制回原数组
for(int ii=0;ii<k;ii++){
a[left + ii] = temp[ii];
}
}
7.堆排序
8.基数排序
最高位优先法（MSD）(Most Significant Digit first)
最低位优先法（LSD）(Least Significant Digit first)
如图：
原始序列为：
27 91 1 97 17 23 84 28 72 5 67 25
先按个位排序（个位相同的依次放入一个组内） 排序后为：
91 1 72 23 84 5 25 27 97 17 67 28
在此基础上，按十位排序后：
1 5 17 23 25 27 28 67 72 84 91 97
代码实现
/*
* 基数排序：稳定的排序算法
* arr 代表待排序的数组
* radix 代表基数(比如例子中的10)
* d 代表排序元素的位数
*/
public static void RadixSort(int arr[],int radix,int d){
//临时数组
int temp[]= new int[arr.length];
//count用于记录待排序元素的信息，用来表示该位是i的数的个数
int[] count=new int[radix];
int rate=1;//初始化为1,
//按照低位优先方式，从个位开始遍历，共d位
for(int i=0;i<d;i++){
//重置count数组，开始统计下一个关键字
Arrays.fill(count, 0);
//将arr中的元素完全复制到temp数组中
temp=Arrays.copyOf(arr, arr.length);
//计算每个待排序数据的子关键字
for(int j=0;j<arr.length;j++){
int subkey=(temp[j]/rate)%radix;
count[subkey]++;
}
/*从j等于1开始，统计count数组的前j位(包含j)共有多少个数
* funtion:确定每个元素在排序后数组中的位置
*/
for(int j=1;j<radix;j++){
count[j]=count[j]+count[j-1];
}
//按子关键字对指定的数据进行排序，因为开始是从前往后放，现在从后往前读，保证基数排序的稳定性
for(int m=arr.length-1;m>=0;m--){
int subkey=(temp[m]/rate)%radix;
arr[--count[subkey]]=temp[m];//插入到第--count[subkey]位，因为数组下标从0开始
}
rate*=radix;//前进一位
}
}