排序算法

二分查找算法

概念

二分查找又称为折半查找，它是一种效率较高的查找算法，是一种在有序数组中查找某一特定元素的搜索算法。需要注意的是该算法建立在有序数组基础上。

思想

• 搜索过程是从数组的中间元素开始，若中间元素正好是要查找的元素，则搜索过程结束；
• 若某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素进行比较；
• 退出的条件就是数组为空或找到元素。

这种查找算法没进行一次查找都事搜索范围缩小一半。

递归实现

public static <E extends Comparable<E>> int binarySearch(E[] array, int from, int to, E key) {
    if (from < 0 || to < 0) {
        throw new IllegalArgumentException("params from & to must larger than 0.");
    }

    if (from <= to) {
        int middle = (from >>> 1) + (to >>> 1);
        E temp = array[middle];
        if (key.compareTo(temp) > 0) {
            from = middle + 1;
        } else if (key.compareTo(temp) < 0) {
            to = middle - 1;
        } else {
            return middle;
        }
    }

    return binarySearch(array, from, to, key);
}

非递归实现

public static int binarySearch(int[] array, int from, int to, int key) {
    while (from <= to) {
        int mid = (from + to) >>> 1;
        int midVal = array[mid];
        if (midVal < key) {
            from = mid + 1;
        } else if (midVal > key) {
            to = mid - 1;
        } else {
            return mid;
        }
    }
    return -(from + 1);
}

冒泡排序

每当相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。

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

冒泡排序改进

添加标志变量

对于基本有序的数组，常见的改进方法是加入标志性变量，用于标志某一趟排序过程是否有数据交换。若某一趟排序没有数据交换，这说明数据已经排好序了，可以结束排序。具体做法：设置一标志性变量pos，用于记录每趟排序中最后一次进行交换的位置。由于pos位置之后的记录均已交换到位，故在进行下一趟排序时只要扫描到pos位置即可。

public static void bubbleSort2(int[] array) {
    int i = array.length - 1;
    while (i > 0) {
        int pos = 0;
        for (int j = 0 ; j < i; j++) {
            if (array[j] > array[j + 1]) {
                pos = j;
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
        i = pos;
    }
}

双向冒泡

传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值，考虑利用在每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值(最大值或最小值)，从而使排序趟数几乎减少一半。

public static void bubbleSort3(int[] array) {
    int low = 0;
    int high = array.length - 1;//设置初始值
    int tmp, j;

    while (low < high) {
        for (j = low; j < high; j++) {
            if (array[j] > array[j + 1]) {//正向冒泡找出最大值
                tmp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = tmp;
            }
        }
        high--;//修改high值，向前以一位
        for (j = high; j > low; j--) {
            if (array[j] < array[j + 1]) {//反向冒泡找出最小值
                tmp = array[j];
                array[j] = array[j - 1];
                array[j - 1] = tmp;
            }
        }
        low++;//修改low值，向后移一位
    }
}

快速排序

思想：选择一个基准元素，通常选择第一个元素或最后一个元素，通过一趟排序将待排序的记录分割成独立的两部分，其中一部分记录的元素比基准值小，另一部分记录的元素比基准值大；此时基准元素在其排好序后的正确位置；然后分别对这两部分记录用同样的方法进行排序，直到整个排序有序。

递归实现

public void quickSort(int[] arr, int low, int high) {
    if(low < high) {
        int pivot = partition(arr, low, high);
        quickSort(arr, low, pivot - 1);
        quickSort(arr, pivot + 1, high);
    }
}

public int partition(int[] arr, int low, int high) {
    int pivot = arr[low];
    int temp;

    while(low < high) {
        while(low < high && arr[high] >= pivot) {
            high--;
        }
        if(low < high) {
            temp = arr[low];
            arr[low] = arr[high];
            arr[high] = temp;
        }

        while(low < high && arr[low] <= pivot) {
            low++;
        }

        if(low < high) {
            temp = arr[low];
            arr[low] = arr[high];
            arr[high] = temp;
        }

    }
    return low;
}

插入排序

思想：通过构建有序序列，对未排序数据，在已排序序列中从后向前扫描，找到相应位置插入。非常类似整扑克牌，在开始摸牌阶段，左手是空的，一次从桌子上摸起一张牌，并将它插入到左手一把牌中正确的位置。为了找到这张牌的正确位置，要将它与手中已有的牌进行比较。无论什么时候，左手的牌都是好的。若数组是已经排好序的，插入排序出现最佳情况，其时间复杂度是线性的。若是逆序的情况，则出现最坏情况，其时间复杂度是n平方级的，平均情况和最坏情况一样。

描述：假设第一个元素被放置在正确的位置，这样仅需从1到n - 1 范围内对剩余元素进行排序。对于每次遍历，从0到i-1范围内的元素已经被排好序。每次遍历的任务是：通过扫描前面已经排序的子列表，将位置i处的元素定位到从0到i的子列表之内的正确的位置上。

public void insertSort(int[] arr) {
    int i, j;
    int n = arr.length;
    int target;
    for(int i = 1; i < n; i++) {
        j = i;
        target = arr[i];

        while(j > 0 && target < arr[j - 1]) {
            arr[j] = arr[j - 1];
            j--;
        }
        arr[j] = target;
    }

}

选择排序

思想：在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。

描述：第一趟，从n个记录中找出关键码最小的记录与第一个记录交换；第二趟，从第二个记录开始的n-1个记录中再选出关键码最小的记录与第二个记录交换；以此类推，直到整个序列按照关键码有序排序。

pulib void selectSort(int[] arr) {
    int n = arr.length;
    int key,temp;
    int j;
    int i;

    for(i = 0; i < n - 1; i++) {
        key  = i;
        for(j = i + 1;j < n;j++) {
            if(arr[j] < arr[key]) {
                key = j;
            }
        }
        if(key != i) {
            temp = arr[i];
            arr[i] = arr[key];
            arr[key] = temp;
        }
    }

}