冒泡排序、选择排序、插入排序、shell排序、快速排序和归并排序的原理及其实现

分析并实现了各种排序算法

冒泡排序算法:

冒泡排序算法是最简单的排序算法,是一种典型的交换排序算法。其原理是,实现了双层循环,内层循环将相邻两个数进行两两比较,将最大的一个数以冒泡(两两交换)的形式传送最队尾,一次只能将一个最大值传送到队尾;而外层循环实现了依次将当前最大值传送,最终实现排序;

实现代码:

/**
     * 冒泡排序算法
     * @param source
     */
    public static void bubbleSort(int[] source){
        int length = source.length;
        for (int i = 0; i < length-1; i++){
            for (int j = 0; j < length-1-i; j++){
                if (source[j] > source[j+1]){
                    swap(source, j, j+1);
                }
            }
        }
    }

    /**
     * 执行交换
     * @param source
     * @param x
     * @param y
     */
    public static void swap(int[] source, int x, int y){
        int temp = source[x];
        source[x] = source[y];
        source[y] = temp;
    }

选择排序算法:

原理:首先在未排序序列中找到最小的元素,存放到排序序列的起始位置,然后,再从剩余未排序的元素中寻找最小的元素,放到排序序列起始位之后。依次类推,直到所有的元素均排序完毕。

实现代码:

public static void selectSort(int[] source){
        int length = source.length;
        for (int i = 0; i < length; i++) {
            for (int j = i + 1; j < length; j++){
                if (source[i] > source[j]){
                    swap(source, i, j);
                }
            }
        }
    }

    /**
     * 执行交换
     * @param source
     * @param x
     * @param y
     */
    public static void swap(int[] source, int x, int y){
        int temp = source[x];
        source[x] = source[y];
        source[y] = temp;
    }

插入排序算法:

原理:

插入排序算法有种递归的思想在里面,它由N-1趟排序组成。初始时,只考虑数组下标0处的元素,只有一个元素,显然是有序的。

然后第一趟 对下标 1 处的元素进行排序,保证数组[0,1]上的元素有序;

第二趟 对下标 2 处的元素进行排序,保证数组[0,2]上的元素有序;

.....

.....

第N-1趟对下标 N-1 处的元素进行排序,保证数组[0,N-1]上的元素有序,也就是整个数组有序了。

它的递归思想就体现在:当对位置 i 处的元素进行排序时,[0,i-1]上的元素一定是已经有序的了。

实现程序:

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

    /**
     * 执行交换
     * @param source
     * @param x
     * @param y
     */
    public static void swap(int[] source, int x, int y){
        int temp = source[x];
        source[x] = source[y];
        source[y] = temp;
    }

希尔排序算法:

希尔(Shell)排序又称为缩小增量排序,它是一种插入排序。它是直接插入排序算法的一种威力加强版。

原理:根据一定的步长,将数据进行分组,然后对每组进行排序,在每一组数据都有序之后,缩小分组的步长,继续进行组内排序,直到步长缩短为0,相应的排序也就结束了。他可以显著的减少数据交换次数,加快排序速度。

在上面这幅图中:

初始时,有一个大小为 10 的无序序列。

在第一趟排序中,我们不妨设 gap1 = N / 2 = 5,即相隔距离为 5 的元素组成一组,可以分为 5 组。接下来,按照直接插入排序的方法对每个组进行排序。

在第二趟排序中,我们把上次的 gap 缩小一半,即 gap2 = gap1 / 2 = 2 (取整数)。这样每相隔距离为 2 的元素组成一组,可以分为 2 组。按照直接插入排序的方法对每个组进行排序。

在第三趟排序中,再次把 gap 缩小一半,即gap3 = gap2 / 2 = 1。 这样相隔距离为 1 的元素组成一组,即只有一组。按照直接插入排序的方法对每个组进行排序。此时,排序已经结束。

需要注意一下的是,图中有两个相等数值的元素 5 和 5 。我们可以清楚的看到,在排序过程中,两个元素位置交换了。

所以,希尔排序是不稳定的算法。

实现代码:

public static void shellSort(int [] source){
        int gap = source.length/2;
        while (gap>=1){
            for (int i = gap; i < source.length; i++) {
                if (source[i] < source[i-gap]){
                    //缓存当前值
                    int temp = source[i];
                    int j;
                    //直接插入算法,找到当前值的排序位置,将数组后移到分组的点,最后将缓存值差插入合适的位置
                    for (j = i - gap; (j >= 0) && (temp < source[j]); j -= gap){
                        source[j + gap] = source[j];
                    }
                    source[j + gap] = temp;
                }
            }
            System.out.format("gpa = %d: ", gap);
            printAll(source);
            gap = gap/2;
        }
    }

    // 打印完整序列
    public static void printAll(int[] list) {
        for (int value : list) {
            System.out.print(value + " ");
        }
        System.out.println();
    }

快速排序算法:

原理:选择一个数组值作为基准,从数组两边开始遍历整个数组,我们选取一个基准值,从右侧开始遍历,找到小于基准的数,就替换掉基准位的值,接下来从左开始遍历,找到大于基准的值,就填补右侧之前替换掉基准位的值的位置空缺,左右的遍历依次交换进行,直到左右两个遍历相遇,将基准值放入相遇的位置。此时左侧全部为小于基准的值,右侧全为大于基准的值。之后对于前后段的排序也递归采用前面的方式,直到排序结束。

假设我们初始值为“6 1 2 7 9 3 4 5 10 8”,选取6作为基准,其第一次快排的结果是“5 1 2 4 3 6 9 7 10 8”。

 

实现程序:

/**
     * 快速排序
     * @param source 排序数组
     * @param a 起始点
     * @param b 结束点
     */
    public static void quickSort(int [] source, int a, int b){
        if (!(a < b)) return;
        int i = a;
        int j = b;
        int x = source[i];
        while (i < j){
            //循环递减,直到i、j相遇或者出现小于基准数的值
            while (i < j && source[j] > x){
                j--;
            }
            if (i < j){
                source[i] = source[j];
                i++;
            }
            //循环递增,直到出现大于基准数的值
            while (i < j && source[i] < x){
                i++;
            }
            if (i < j){
                source[j] = source[i];
                j--;
            }
        }
        //将基准点位移到中间位置
        source[i] = x;
        System.out.println(source);
        //递归调用,基准点前的排序;之后进行基准点之后的排序
        quickSort(source, a, i-1);
        quickSort(source, i+1, b);
    }

归并排序算法:

原理:首先使用分割法将这个序列分割成一个一个已经排好了序的子序列,然后利用归并的方法将一个一个的子序列合并成排好的序列。示意图如下:

实现程序:

public static void sort(int []arr){
        int []temp = new int[arr.length];
        //在排序前,先建好一个长度等于原数组长度的临时数组,
        //避免递归中频繁开辟空间
        margeSort(arr,0,arr.length-1,temp);
    }

    public static void margeSort(int[] arr, int left, int right, int []temp){
        if(left<right){
            int mid = (left+right)/2;
            margeSort(arr,left,mid,temp);
            //左边归并排序,使得左子序列有序
            margeSort(arr,mid+1,right,temp);
            //右边归并排序,使得右子序列有序
            merge(arr,left,mid,right,temp);
            //将两个有序子数组合并操作
        }
    }
    public static void merge(int[] arr,int left,int mid,int right,int[] temp){
        int i = left;//左序列指针
        int j = mid+1;//右序列指针
        int t = 0;//临时数组指针
        while (i<=mid && j<=right){
            if(arr[i]<=arr[j]){
                temp[t++] = arr[i++];
            }else {
                temp[t++] = arr[j++];
            }
        }
        while(i<=mid){//将左边剩余元素填充进temp中
            temp[t++] = arr[i++];
        }
        while(j<=right){//将右序列剩余元素填充进temp中
            temp[t++] = arr[j++];
        }
        t = 0;
        //将temp中的元素全部拷贝到原数组中
        while(left <= right){
            arr[left++] = temp[t++];
        }
    }

参考文献:

java之音网站;

CSDN网站博客;

微信公众号: 后端技术精选。

 

发表评论