首页 > 代码库 > 几种基础排序算法的实现(Java C++)

几种基础排序算法的实现(Java C++)

  最近在复习数据结构/算法,准备把以前的基础知识都实现一边,过一过。也写写我人生中的第一篇技术博文…只求自己能把学过的东西梳理一便,加深记忆。

一、插入排序。

  设计思想:从数组的第二个元素开始循环,并将此元素设为key(通俗的理解就是数组中正在为它排序的元素),再把此元素与之前的所有已经排好序的元素进行比较,找到合适的位置后,继续循环,直到数组中的最后一个元素为止。

(C++)

 1 void insertSort(int *array, int length) {
 2     for (int i = 1; i < length; i++) {
 3         int key = array[i];
 4         int j = i - 1;
 5         while (j >= 0 && array[j] > key) {
 6             array[j + 1] = array[j];
 7             array[--j + 1] = key;
 8         }
 9     }
10 }

(Java)

public static void insertSort(int[] array) {
        if (array == null) {
            return;
        }
        if (array.length <= 1) {
            return;
        }
        for (int i = 1; i < array.length; i++) {
            int key = array[i];
            int j = i - 1;
            while (j >= 0 && key < array[j]) {
                array[j + 1] = array[j];
                array[--j + 1] = key;
            }
        }
    }

在插入排序的实现中,把二层循环的判断条件设置为递减而不是递增,可以有效的提高算法的效率。

  试想, j 为 0到 i-1 递增判断,设当前的 key 在x位 (0...x...i-1  — [0,i-1] 是数组中已经排序号的部分),递增判断则需要首先从0到x找到 x位,然后再进行 x+1 到 i 的数组移位,最后再将 key 放置到 x位上。

  而为递减判断时,key 跟随 j 一起向后数组的头部移动,而当遇到小于 key 的元素时, while循环 停止。相比比递增判断,递减判断只需要移位的时间,就可以找到key所在的位置了。

二、冒泡排序

  设计思想:冒泡排序是通过元素的顺序两两比较,再将较大的元素推到数组的尾部,过程就像冒泡一样,经过一次遍历后,就可以得到一个有序的数组。

(C++)

void bubbleSort(int *array, int length) {
    int temp;
    for (int i = 0; i < length; i++) {
        for (int j = length - 1; j > i; j--) {
            if (array[i] > array[j]) {
                temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
    }
}

 

(Java)

 1 public static void bubbleSort(int[] array) {
 2         for (int i = 0; i < array.length - 1; i++) {
 3             for(int j = array.length - 1 ; j > i ; j -- ) {
 4                 if(array[j] < array[j-1]) {
 5                     int temp = array[j-1];
 6                     array[j-1] = array[j];
 7                     array[j] = temp;
 8                 }
 9             }
10         }
11     }

以上的冒泡排序算法也和插入排序一样,使用了 j 递减条件来提高算法效率,因为 j 的初值与 i 的值相关联。可以通过将已排序好的数值推到i的前面,就可以有效的去掉未排序数与已排序好的数组元素比较,从而提高算法的效率。

几种基础排序算法的实现(Java C++)