常见排序算法

排序算法

  • 归并排序[联想到合并两个有序的数组] http://flyingcat2013.blog.51cto.com/7061638/1281026

    // 归并排序
    public static void mergeSort(int[] arr){
            // 创建一个临时数组,用来存储合并之后的数组
            int[] temp =new int[arr.length];
            internalMergeSort(arr, temp, 0, arr.length-1);
    }
    
    private static void internalMergeSort(int[] a, int[] b, int left, int right){
            // 当left==right的时,已经不需要再划分了
            if (left<right){
                int middle = (left+right)/2;
                internalMergeSort(a, b, left, middle);          //左子数组
                internalMergeSort(a, b, middle+1, right);       //右子数组
                mergeSortedArray(a, b, left, middle, right);    //合并两个子数组
            }
        }
    
    // 合并两个有序子序列 arr[left, ..., middle] 和 arr[middle+1, ..., right]。temp是辅助数组。
    private static void mergeSortedArray(int arr[], int temp[], int left, int middle, int right){
            int i=left;     
            int j=middle+1;
            int k=0;
      // 这里的核心就是合并两个有序数组,谁大放进新的数组
            while ( i<=middle && j<=right){
                if (arr[i] <=arr[j]){
                    temp[k++] = arr[i++];
                }
                else{
                    temp[k++] = arr[j++];
                }
            }
      // 左边的还有剩余
            while (i <=middle){
                temp[k++] = arr[i++];
            }
      // 右边的还有剩余
            while ( j<=right){
                temp[k++] = arr[j++];
            }
      // 把数据复制回原数组
            for (i=0; i<k; ++i){
                arr[left+i] = temp[i];
            }
        }
    
  • 希尔排序又称缩小增量排序

    public static void shellSort(int[] arr){
        int temp;
        for (int delta = arr.length/2; delta>=1; delta/=2){                              //对每个增量进行一次排序
            for (int i=delta; i<arr.length; i++){             
                for (int j=i; j>=delta && arr[j]<arr[j-delta]; j-=delta){ //注意每个地方增量和差值都是delta
                    temp = arr[j-delta];
                    arr[j-delta] = arr[j];
                    arr[j] = temp;
                }
            }//loop i
        }//loop delta
    }
    
  • 堆排序 http://flyingcat2013.blog.51cto.com/7061638/1283090

    • 如何初始化一个堆
    • 排序过程中如何去调整堆
    • 堆排序存在大量的筛选和移动过程,属于不稳定的排序算法。
    • 适用于解决前 n 大的算法
    public class HeapSort {
        //对data数组从0到lastIndex建大顶堆
        public static void buildMaxHeap(int[] data, int lastIndex){
            //从lastIndex处节点(最后一个节点)的父节点开始
            // http://bubkoo.com/2014/01/14/sort-algorithm/heap-sort/
            for(int i=(lastIndex-1)/2;i>=0;i--){
                //k保存正在判断的节点
                int k=i;
                //如果当前k节点的子节点存在,lastIndex 是最后一个节点的索引,不是其父节点的索引,要注意
                while(k*2+1<=lastIndex){
                    //k节点的左子节点的索引
                    int biggerIndex=2*k+1;
    
                    //如果biggerIndex小于lastIndex,即biggerIndex+1代表的k节点的右子节点存在
                    if(biggerIndex<lastIndex){
                        //若果右子节点的值较大
                        if(data[biggerIndex]<data[biggerIndex+1]){
                            //biggerIndex总是记录较大子节点的索引
                            biggerIndex++;
                        }
                    }
    
                    //如果k节点的值小于其较大的子节点的值
                    if(data[k]<data[biggerIndex]){
                        //交换他们
                        swap(data,k,biggerIndex);
                        //将biggerIndex赋予k,开始while循环的下一次循环,重新保证k节点的值大于其左右子节点的值
                        // 要将最大的或者最小的一直往上顶上去
                        k=biggerIndex;
                    }else{
                        break;
                    }
                }
            }
        }
        //交换
        private static void swap(int[] data, int i, int j) {
            int tmp=data[i];
            data[i]=data[j];
            data[j]=tmp;
        }
    
        public static void main(String[] args) {
            int[] a={49,38,65,97,76,13,27,49,78,34,12,64};
            int arrayLength=a.length;
            //循环建堆
            for(int i=0;i<arrayLength-1;i++){
                //建堆
                buildMaxHeap(a,arrayLength-1-i);
                //交换堆顶和最后一个元素
                swap(a,0,arrayLength-1-i);
                System.out.println(Arrays.toString(a));
            }
        }
    } 
    
  • 选择排序

    设现在要给数组arr[]排序,它有n个元素。

    • 对第一个元素(Java中,下标为0)和第二个元素进行比较,如果前者大于后者,那么它一定不是最小的,但是我们并不像冒泡排序一样急着交换。我们可以设置一个临时变量a,存储这个目前最小的元素的下标。然后我们把这个目前最小的元素继续和第三个元素做比较,如果它仍不是最小的,那么,我们再修改a的值。如此直到和最后一个元素比较完,可以肯定a存储的一定是最小的元素的下标。
    • 如果a的值不为0(初始值,即第一个元素的下标),交换下标为a和0的两个元素。
    • 重复上述过程,这次从下标为1的元素开始比较,因为下标为0的位置已经放好了最小的元素了。
    • 如此直到只剩下最后一个元素,可以肯定这个元素就是最大的了。
    public static void selectionSort(int[] arr) {
            int temp, min = 0;
            for (int index = 0; index < arr.length - 1; ++index) {
                min = index;
                // 循环查找最小值
                for (int j = index + 1; j < arr.length; ++j) {
                   // 如果比当前的小,就交换,不是的话就算了,继续
                    if (arr[min] > arr[j]) {
                        min = j;
                    }
                }
                // 把最小的与 index 位置元素交换
                if (min != index) {
                    temp = arr[index];
                    arr[index] = arr[min];
                    arr[min] = temp;
                }
            }
        }
    
  • 冒泡排序 http://flyingcat2013.blog.51cto.com/7061638/1279334

    设现在要给数组arr[]排序,它有n个元素。

    1.如果n=1:显然不用排了。

    2.如果n>1:

    1)我们从第一个元素开始,把每两个相邻元素进行比较,如果前面的元素比后面的大,那么在最后的结果里面前者肯定排在后面。所以,我们把这两个元素交换。然后进行下两个相邻的元素的比较。如此直到最后一对元素比较完毕,则第一轮排序完成。可以肯定,最后一个元素一定是数组中最大的(因为每次都把相对大的放到后面了)。

    2)重复上述过程,这次我们无需考虑最后一个,因为它已经排好了。

    3)如此直到只剩一个元素,这个元素一定是最小的,那么我们的排序可以结束了。显然,进行了n-1次排序。

    上述过程中,每次(或者叫做“轮”)排序都会有一个数从某个位置慢慢“浮动”到最终的位置(画个示意图,把数组画成竖直的就可以看出来),就像冒泡一样,所以,它被称为“冒泡排序法”。

    public static void bubbleSort(int[] arr) {
        int temp = 0;
        for (int i = arr.length - 1; i > 0; --i) { // 每次需要排序的长度
            for (int j = 0; j < i; ++j) { // 从第一个元素到第i个元素
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }//loop j
        }//loop i
    }// method bubbleSort
    
  • 快速排序

    • 快排的思想很简单,从左到右依次往中间前进
    • 复杂度要记住为 O(n logn)
    public static void quickSort(int[] arr){
        qsort(arr, 0, arr.length-1);
    }
    private static void qsort(int[] arr, int low, int high){
        if (low < high){
            int pivot=partition(arr, low, high);        //将数组分为两部分
            qsort(arr, low, pivot-1);                   //递归排序左子数组
            qsort(arr, pivot+1, high);                  //递归排序右子数组
        }
    }
    private static int partition(int[] arr, int low, int high){
        int pivot = arr[low];     //枢轴记录
        while (low<high){
            while (low<high && arr[high]>=pivot) --high;
            arr[low]=arr[high];             //交换比枢轴小的记录到左端
            while (low<high && arr[low]<=pivot) ++low;
            arr[high] = arr[low];           //交换比枢轴小的记录到右端
        }
        //扫描完成,枢轴到位,注意这时候 low 已经前进到中间的位置了
        arr[low] = pivot;
        //返回的是枢轴的位置
        return low;
    }
    
  • 插入排序

    • 把待排序的数组分成已排序和未排序两部分,初始的时候把第一个元素认为是已排好序的。
    • 从第二个元素开始,在已排好序的子数组中寻找到该元素合适的位置并插入该位置。
    • 重复上述过程直到最后一个元素被插入有序子数组中。
    • 排序完成。
    public static void insertionSort(int[] arr){
      // 注意 i = 1 开始排序的,即从第二个元素开始
        for (int i=1; i<arr.length; ++i){
           // 每次拿的未排序的数组中的一个元素,来与前面的比较
            int value = arr[i];
            int position;
            // 依次与前面的每个元素进行比较
            for (position=i; position>0 ; --position){
                // 如果比前面的元素小,前面的元素就自动向后面退一位
                if (arr[position-1] > value){
                    arr[position]=arr[position-1];
                }
                // 如果比前面的元素大,前面的元素不用动,这次循环结束
                else{
                    break;
                }
            }
            // 将未排序的元素插入到指定的位置
            arr[position] = value;
        }
    }
    
欢迎添加我的微信与我交流