美文网首页
排序算法

排序算法

作者: zxcvbnmzsedr | 来源:发表于2017-07-12 20:36 被阅读0次

    一、插入排序

    1、直接插入

    直接插入排序类似于扑克牌,分为两块,一块是排完序的,一块是没有进行排序的。
    例如下面四个元素的数组,| 的左边的有序的,右边是无序的。

    3 | 1 4 2
    1 3 | 4 2
    1 3 4 | 2
    1 2 3 4 |
    

    默认左边第一个数是有序的排序的时候从 | 的右边取一个数,如果比左边的小则交换,一直交换到数组下标为1。
    i 代表 | ,j代表从 | 右边取出的元素
    代码实现:

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

    这种算法有缺陷,每次对比都要交换元素
    改进:

      public int[] insertionSort(int[] a) {
            for (int i = 1; i < a.length; i++) {
                int temp = a[i];
                int j = i - 1;
                for (; j >= 0 && a[j] > temp; j--) {
                    a[j + 1] = a[j];
                }
                a[j + 1] = temp;
            }
            return a;
        }
    
    使用插入排序为一列数字进行排序的过程

    二、选择排序

    1、直接选择

    首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

    选择排序的示例动画。红色表示当前最小值,黄色表示已排序序列,蓝色表示当前位置。
      public void selectionSort(int[] a){
            for(int i=0;i<a.length;i++){
                int min = i;
                for(int j = i+1;j<a.length;j++){
                    if(a[min]>a[j]){
                        min = j;
                    }
                }
                int temp = a[min];
                a[min] = a[i];
                a[i] = temp;
            }
        }
    

    三、交换排序

    1、冒泡排序

    冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。


    1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
    2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
    3. 针对所有的元素重复以上的步骤,除了最后一个。
    4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
     public void bubbleSort(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]){
                        swap(a,j,j+1);
                    }
                }
            }
     }   
    

    2、快速排序

    排序数组时,将数组划分成两个较小的部分,然后递归排序他们。


    在一个元素55处划分,把小于55的放在左边,大于55的放在右边。



    然后在分别递归左边和右边的数组,即可完成排序

        public int[] qSort(int[] a, int start, int end) {
            if (a == null||a.length == 0) {
                return null;
            }
            if (start >= end) {
                return a;
            }
            int middel = partition(a, start, end);
            qSort(a, start, middel - 1);
            qSort(a, middel+1, end);
            return a;
        }
        public int partition(int[] data, int low, int high) {
            int temp = data[low]; // 轴记录
            while (low < high) {
                while (low < high && data[high] >= temp) {
                    --high;
                }
                data[low] = data[high];             //交换比枢轴小的记录到左端
                while (low < high && data[low] <= temp) {
                    ++low;
                }
                data[high] = data[low];           //交换比枢轴小的记录到右端
            }
            //扫描完成,枢轴到位
            data[low] = temp;
            //返回的是枢轴的位置
            return low;
        }
    

    相关文章

      网友评论

          本文标题:排序算法

          本文链接:https://www.haomeiwen.com/subject/nucihxtx.html