常见排序方法实现

冒泡排序

思想就是小的数不停地往上（前）冒，程序实现是第i轮从后往前依次比较相邻两数大小，如果小的数在靠后位置就交换两数，这样这一轮最小的数就冒泡到了i的位置。

    public static void bubbleSort(int[] a){
        for(int i = 0; i < a.length - 1; ++i){
            for(int j = a.length - 1; j > i; --j){
                if(a[j] < a[j-1]){
                    int temp = a[j];
                    a[j] = a[j-1];
                    a[j-1] = temp;
                }
            }
        }
    }

开始我对冒泡排序的理解其实是下沉排序的思想，于是顺手写了个下沉排序：

    public static void sinkSort(int[] a){
        for(int i = 0; i < a.length - 1; ++i){
            for(int j = 0; j < a.length - i - 1; ++j){
                if(a[j] > a[j+1]){
                    int temp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = temp;
                }
            }
        }
    }

选择排序

我个人认为最好理解最好实现的一种排序算法，思想就是第i轮从未排序的序列中找到最小的，跟第i个数交换。

public static void selectSort(int[] a){
        for(int i = 0; i < a.length - 1; ++i){
            int min = a[i], minIndex = i;   
            for(int j = i+1; j < a.length; ++j){
                if(a[j] < min){
                    min = a[j];
                    minIndex = j;
                }
            }
            if(minIndex != i){
                int temp = a[i];
                a[i] = min;
                a[minIndex] = temp;
            }
        }
    }

插入排序

思想就是对前面已排好序的序列，寻找合适的位置插入进去。程序怎么实现插入呢？就是想象把待插入的数挖出来，从后往前寻找，每发现当前位置不是合适的位置就把当前位置的数往后挪一个位置，最后发现合适的位置把待插入的数塞进去。要注意的是j开始的位置就是待插入数位置的前一个，并且每次发现不合适要减一，所以最后发现合适位置时应该+1回到当前位置。

public static void insertSort(int[] a){
        for(int i = 1; i < a.length; ++i){      
            int j = i - 1;
            int temp = a[i];
            while(j >= 0 && temp < a[j]){
                a[j+1] = a[j--];
            }
            a[++j] = temp;
        }
    }

归并排序

（二路归并）就是（递归）将数组平分成两部分，每部分实现有序，再把两数组合并。在合并时需要用一个新数组来存储合并结果，所以需要额外O(n)空间。

public static void merge(int[] a, int start, int mid, int end){
        int[] temp = new int[end - start + 1];
        
        int i = start, j = mid+1, k = 0;
        while(i <= mid && j <= end){
            if(a[i] < a[j]){
                temp[k++] = a[i++];
            }else{
                temp[k++] = a[j++];
            }
        }
        
        
        while(i <= mid){
            temp[k++] = a[i++];
        }
        while(j <= end){
            temp[k++] = a[j++];
        }
        
        for(i = start; i <= end; ++i){
            a[i] = temp[i-start];
        }
    }
    
    
    public static void mergeSort(int[] a, int start, int end){
        if(start < end){
            int mid = (end - start)/2 + start;
            mergeSort(a,start,mid);
            mergeSort(a,mid+1,end);
            merge(a,start,mid,end);
        }
    }

快速排序

思想是取一个pivot，让待排序数组变成所有小于pivot的数放pivot左边，其他放右边。程序怎样实现呢？假设pivot是待排序的第一个数，想象给它挖一个坑，从后往前找一个比pivot小的数来填前面这个坑，再从前往后找一个比pivot大于等于的数来填后面的坑；循环进行，最后剩下的一个坑就是pivot位置。

    public static void quickSort(int[] a, int start, int end){
        
        if(start < end){
            int pivot = a[start];
            int left = start, right = end;
            
            
            while(left < right){
                while(left < right && a[right] >= pivot){
                    --right;
                }
                if(left < right && a[right] < pivot){
                    a[left++] = a[right];
                }
                
                while(left < right && a[left] < pivot){
                    ++left;
                }
                if(left < right && a[left] >= pivot){
                    a[right--] = a[left];
                }
            }
            
            a[left] = pivot;
            
            quickSort(a,start,left-1);
            quickSort(a,left+1,end);
        }
    }
    
}

还差一个对我来说比较难的堆排序，抽时间一定要写出来啊！！！！！！！

常见排序方法实现