1. 概览

  • 稳定性:一般基于相邻交换的原理的排序算法,是稳定的
  • 时间复杂度:基于分治原理的排序算法是O(nlogn),有特殊使用场景的排序算法可以在O(n)

2. 冒泡排序

原理概述(按照升序来解释):a[i]和a[i+1]比较,如果a[i]比较大,就进行交换,这样不断比较,就可以把最大的值冒到最后。这样就完成了一轮冒泡。

稳定性:基于相邻比较,所以稳定

    //冒泡排序
    public static void bubbleSort(int[] a){
        int len = a.length;                     //标记数组长度
        for(int i=0;i<len-1;i++){
            for(int j=0;j<len-i-1;j++){
                if(a[j]>a[j+1]){                //交换函数,使用异或来比较效率更高
                    a[j]=a[j]^a[j+1];
                    a[j+1]=a[j]^a[j+1];
                    a[j]=a[j]^a[j+1];
                }
            }
        }
    }

3. 选择排序

原理概述:第i次选择,选出第i小的数,放在第i个位置

稳定性:不是相邻交换,不稳定

    //选择排序
    public static void  selectionSort(int[] a){
        int len = a.length;

        for(int i=0;i<len;i++){
            int index = i;                            //用于记录一次循环找到的最小的值的小表,一开始默认为i
            for(int j=i;j<len;j++){
                if(a[j]<a[index]) index=j;                  //发现更小的值就记录其下标
            }

            if(index!=i) {     //如果发现i的值有过变化,就要进行交换
                a[i]=a[i]^a[index];
                a[index]=a[i]^a[index];
                a[i]=a[i]^a[index];
            }
        }
    }

4. 插入排序

原理概述:从前面的有序序列从尾到头进行比较,如果更小就交换,如果更大就直接break。通过不断比较实际上找到了插入的位置。(其实也是基于比较的)

稳定性:基于相邻比较,是稳定的

    public static void insertionSort(int[] a){
        int len = a.length;
        for(int i=0;i<len-1;i++){
            for(int j=i;j>=0;j--){          //这里要注意是>=0,这样a[1]和a[0]的比较不会漏掉
                if(a[j+1]<a[j]){        //每次和前面的有序数列从后往前比较,如果更小则交换,其实在多次交换过程中完成了后移
                    a[j+1]=a[j+1]^a[j];
                    a[j]=a[j+1]^a[j];
                    a[j+1]=a[j+1]^a[j];
                }
                else break;
            }
        }
    }

5. 快速排序

原理概述:选定第一个数为基准值,设定left和right指针,相向移动,直到找到一对符合交换条件的值,进行交换,如此持续直到left>right的时候把基准值和a[right]值交换,将基准值两边的部分再调用递归函数来计算

不是基于相邻交换的方式,不稳定。

    //快速排序
    public static void quickSort(int[] a, int left,int right){
        if(left>right)   return;     //出递归条件
        int start = left;          //记录开始的下标
        int end = right;            //记录结束的下标
        int baseValue = a[left];       //取第一个值为比较的基准值,比它小的在左边,比它大的在右边
        left++;                         //左边的指针从start+1开始
        while(left<=right){
            while(left<=right && a[left]<=baseValue) left++; //左边开始找到第一个大于基准值的值的下标

            while(left<=right && a[right]>=baseValue)   right--; //右边开始找到第一个小于基准值的值的下标

            if(left<right){          //互相交换
                a[right]=a[right]^a[left];
                a[left]=a[right]^a[left];
                a[right]=a[right]^a[left];
                left++;
                right--;
            }
        }
        //这时候将开始的第一个值,放到当前right下标处,当前a[right]是经过判断的肯定小于等于baseValue,如果等于则不交换
        if(a[right]!=a[start]) {
            a[right] = a[right] ^ a[start];
            a[start] = a[right] ^ a[start];
            a[right] = a[right] ^ a[start];
        }

        //将分出来的两个部分再递归调用函数本身,这时候就把刚才保存初始指针位置的start和end用起来了
        quickSort(a,start,right-1);
        quickSort(a,right+1,end);
    }

6. 希尔排序

也称作缩小增量排序,是插入排序的改进,因为插入排序对基本有序的数列,效率较高,希尔排序也是基于这种特点去优化插入排序的。
原理:设定一个增量d,将n个数分成了d个组,同一个组内的数,保证由于。通过不断缩小d,这种“基本有序”的特征越来越接近“完全有序”。分析希尔排序的比较次数性能等还是数学难题,这里也不多介绍了。

例子:

调整的动态效果见下图:

    public static void shellSort(int[] a){
        int len = a.length;
        int d = len;
        while (d>1){
            d=(d+1)/2;                      //每次增量缩小一半

            for(int i=0;i<len-d;i++){       //注意上界是len-d
                if(a[i+d]<a[i]){        //交换,每次前面的都是有序序列
                    a[i+d]=a[i]^a[i+d];
                    a[i]=a[i]^a[i+d];
                    a[i+d]=a[i]^a[i+d];
                }
            }
        }
    }

7. 归并排序

原理:基于分治法的思想,自顶向上慢慢的去合并排序好的有序子序列。

 //归并排序
    public static void mergeSort(int[] a,int low,int high){
        int mid = (low+high)/2;
        if(low<high){           //出递归条件
            mergeSort(a,low,mid);
            mergeSort(a,mid+1,high);
            merge(a,low,mid,high);
        }
    }

    //归并函数
    public static void merge(int[] a,int low,int mid ,int high){
        int[] aux = new int[high-low+1];            //每次归并需要一个辅助数组,辅助数组长度为low-high+1
        int left = low;                             //左边指针
        int right = mid+1;                          //右边指针
        int i = 0;                                  //标记辅助数组的位置


        while(left<=mid && right<=high){          //指针指向的数如果放入辅助数组则右移动
            aux[i++]=(a[left]<a[right])?a[left++]:a[right++];
        }


        //把左边多出来的数放入辅助数组
        while(left<=mid)    aux[i++] = a[left++];

        //如果是右边多出来的则把右边多出的数放入辅助数组
        while(right<=high)    aux[i++] = a[right++];


        //将辅助数组的有序内容覆盖,原数组中对应位置的数
        for(i = 0;i<aux.length;i++)   a[i+low] = aux[i];
    }

8. 堆排序

堆排序实际上是选择排序的一种改进,通过堆这种数据结构,减少了比较次数(通过建立堆和调整堆)。
原理:

  • 将无序序列构成一个堆