排序算法Java实现

发表于 | 分类于 | | 阅读次数
| 字数统计 2,347

冒泡排序 0(N^2)

执行非常慢，概念上最简单。最大的会一直被交换，冒泡上来

1
2
3
4
5
6
7
8
9
10
11
12
int[] arrays = { 5, 6, 7, 1, 9, 2, 3, 8, 4 };
int out, in;
for (out = arrays.length - 1; out > 1; out--) { // outer loop(backward)
    for (in = 0; in < out; in++) { // inter loop(forward)
        if (arrays[in] > arrays[in + 1]) { // out of order
            int temp = arrays[in]; // swap them
            arrays[in] = arrays[in + 1];
            arrays[in + 1] = temp;
        }
    }
}

选择排序0(N^2)

比较所有的数据项，取出最小值，放左边。比较剩下的数据，取最小，放最左。。。。
内层循环中，每一个in的新位置，数据项a[in]和a[min]比较，如果a[in]更小，则min被赋值为in的值，这里只是下标，没交换。到一次内层循环结束，再交换数据项。这样，最小数据项就会一直被放在左边。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int[] arrays = { 5, 6, 7, 1, 9, 2, 3, 8, 4 };
int out, in, min, nElems = arrays.length;
for (out = 0; out < nElems - 1; out++) { // outer loop
    min = out; // minimum
    for (in = out + 1; in < nElems; in++) { // inner loop
        if (arrays[in] < arrays[min]) { // if min greater
            min = in; // we have a new min
        }
    }
    int temp = arrays[out]; // swap them
    arrays[out] = arrays[min];
    arrays[min] = temp;
}

插入排序 N*(N-1)/2 /2

假设左边部分已经排序好了，从某个位置(比如10)开始无序，将10赋值给一临时值，然后和前面的数据比较，如果9位置比10大，就9右移一位，继续和8比较。。。直到到数据的最左边或找到比10位置数据小的某数据，放在它的右边，10位置的数据就排好了。
在大多数情况下，插入算法仍然需要0(N^2)的时间，但比冒泡快一倍，比选择排序也还要快一点。经常被用在较复杂的排序算法的最后阶段，例如快速排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
int[] arrays = { 5, 6, 7, 1, 9, 2, 3, 8, 4 };
int in, out, nElems = arrays.length;
for (out = 1; out < nElems; out++) { // out is dividing line
    int temp = arrays[out]; // remove marked item
    in = out; // start shifts at out
    while (in > 0 && arrays[in - 1] >= temp)// until one is smaller,
    {
        arrays[in] = arrays[in - 1];// shift item right
        --in;
    }
    arrays[in] = temp; // insert marked item
}

归并排序O(N logN)

只要O(N logN)，而冒泡排序，选择排序，插入排序都要用O(N N);.
归并排序的思想是：将一个数组分成两半，然后分别排序，然后将数组的两半合并，合并的时候需要比较大小(合并的时候还要考虑两小数组还有没有数据，即有可能一边有，另一边没有)。至于如何排序1/2半的数组，当然是再分成两个1/4数组，再排序。。。直到分割的小数组只有1个数据项，不用排序了。这是用到递归的思想
归并排序的缺点，需要在存储器中有另一个大小等于被排序的数据项数目的空间，用来复制分割出来的小数组。
归并算法的效率由来：需要复制log2N层(分子数组)，每一个层都是N个数据，所以是NxlogN.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
private static int[] guibing() {
    int[] arrays = { 5, 6, 7, 1, 9, 2, 3, 8, 4 };
    int[] workSpace = new int[arrays.length];
    recMergeSort(arrays, workSpace, 0, arrays.length - 1);
    return arrays;
}
private static void merge(int[] source, int[] workPlace, int lowPtr, int highPtr, int upperBound){
    int j = 0; // workspace index
    int lowerBound = lowPtr;
    int mid = highPtr - 1;
    int n = upperBound - lowerBound + 1; // size of items
    // 两边都有
    while (lowPtr <= mid && highPtr <= upperBound) {
        if (source[lowPtr] < source[highPtr]) {
            workPlace[j++] = source[lowPtr++];
        } else {
            workPlace[j++] = source[highPtr++];
        }
    }
    // 只有左边
    while (lowPtr <= mid) {
        workPlace[j++] = source[lowPtr++];
    }
    // 只有右边
    while (highPtr <= upperBound) {
        workPlace[j++] = source[highPtr++];
    }
    // 把值复制到原对象
    for (j = 0; j < n; j++) {
        source[lowerBound + j] = workPlace[j];
    }
}
private static void recMergeSort(int[] source, int[] workSpace, int lowerBound, int upperBound) {
    if (lowerBound == upperBound) {
        return;
    } else {
        int mid = (lowerBound + upperBound) / 2;
        recMergeSort(source, workSpace, lowerBound, mid);
        recMergeSort(source, workSpace, mid + 1, upperBound);
        merge(source, workSpace, lowerBound, mid + 1, upperBound);
    }
}

希尔排序

希尔排序基于插入排序，但增加了一个新的特性，大大地提高了插入排序的执行效率。(希尔是个人名。。。)
改进的地方：插入算法中，如果一个数据比较小而居于最右边，那么它需要一个一个地移动所有中间的数据项，效率比较低。
希尔排序通过加入插入排序中元素之间的间隔，并在这些有间隔的元素中进行插入排序，从而使数据项能大跨度地移动。当这些数据项排过一趟序后，减小数据项的间隔。再进行排序，依次进行下去。间隔被称为增量，用h表示.
进行过几次增量排序后，所有的元素离它再最终有序序列中的位置相差不大，数组达到”基本有序”,这时再来插入排序，移动量非常小。
当h值很大的时候，数据项每一趟排序需要移动元素的个数很少，但数据项移动的距离很长，这是非常有效率的。当h减少时，每一趟排序需要移动的元素的个数增多，但是此时数据项已经接近于它们排序后最终的位置，这对于插入排序可以更有效率。
其中，h = h x 3 +1, h = (h -1) / 3,是经验值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int[] arrays = { 5, 6, 7, 1, 9, 2, 3, 8, 4 };
int inner, outer, nElems = arrays.length;
int temp;
int h = 1;
while (h <= nElems / 3) {
    h = h * 3 + 1;
}
while (h > 0) {
    for (outer = h; outer < nElems; outer++) {
        temp = arrays[outer];
        inner = outer;
        while (inner > h - 1 && arrays[inner - h] >= temp) {
            arrays[inner] = arrays[inner - h];
            inner -= h;
        }
        arrays[inner] = temp;
    }
    h = (h - 1) / 3;
}

划分算法

划分是快速排序的根本机制，但是划分本身也是一个有用的操作，这里单讲划分的算法。
划分数据就是把数据分为两组，使所有关键字大于特定值的数据项在一组，使所有关键字小于特定值的数据项在另一组。

划分算法由两个指针开始工作，两个指针分别指向数组的两头。在左边的指针，leftPtr，向右移动，而在右边的指针，rightPtr，向左移动。
实际上，leftPtr初始化时是在第一个数据项的左边一位(-1)，rightPtr是在最后一个数据项的右边一位(size)，这是因为在工作之前，它们都要分别的加一和减一。
停止和交换：当leftPtr遇到比枢纽(特定值，划分值)小的数据项时，它继续右移，因为这个数据项的位置已经处在数组的正确一边了。但是，当遇到比枢纽大的数据项时，它就停下来。类似的，当rightPtr遇到小于枢纽的数据项时，它也停下来。两个内层的while循环，控制这个扫面过程，当两个都停下来时，要么指针到头要么遇到错误的数据(大小比较不对)，做交换(更换位置，正确排列了)。
当两个指针最终相遇的时候，划分过程结束，并且推出这个外层的while循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
private static int[] huafen() {
    int[] arrays = { 5, 6, 7, 1, 9, 2, 3, 8, 4 };
    sort(arrays, 6);
    return arrays;
}
static void sort(int[] ary, int base) {
    int left = 0;
    int right = ary.length - 1;
    int leftpoint = left, rightpoint = right;
    while (true) {
        // 分成左右两边同时进行比较，一边从左向右，一边从右向左，
        while (leftpoint < right && ary[leftpoint++] < base)
            ; // leftpoint大于right或ary[leftpoint]>base停止循环
        while (rightpoint >= left && ary[rightpoint--] > base)
            ; // 反之
        System.out.println("左边需要交换的索引:" + (leftpoint - 1));
        System.out.println("右边需要交换的索引:" + (rightpoint + 1));
        // 上面拿到了不符合条件的两个索引，即需要交换的两个索引
        if (leftpoint - 1 < rightpoint + 1) {// 需要交换
            int temp = ary[leftpoint - 1];
            ary[leftpoint - 1] = ary[rightpoint + 1];
            ary[rightpoint + 1] = temp;
            leftpoint = left;
            rightpoint = right;
        } else {
            break;
        }
    }
}

快速排序

最流行的排序算法，时间复杂度为O(N*logN)。虽然不觉得这种行为好，但有的公司喜欢笔试时让人手写快排(一些开发者如是说)。
原理是：把一个数组划分为两个子数组，这里用到划分算法，左子数组的数据项都小于右子数组的数据项，然后递归地调用自身为每个子数组进行快速排序来实现，最后使用插入排序。

在这个算法中划分的关键值(枢纽)的选择非常重要。
最初思想，选用数组最右边的值为pivot,进行一次划分，划分的结果就是left->mid-1, mid->right-1, right(这个位置的值是pivot)，三部分，然后交换mid和right的值(划分算法的leftPtr在停止时会停在mid位置)，这样pivot就到中间，而小于pivot的值全在左边，大于的值全在右边，数组的排序不受影响。
下面的排序从left到pivot-1,pivot+到right。中间项不参与划分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public static int[] quickSort() {
    int[] arrays = { 5, 6, 7, 1, 9, 2, 3, 8, 4 };
    qsort(arrays, 0, arrays.length - 1);
    return arrays;
}
private static void qsort(int[] arr, int low, int high) {
    if (low < high) {
        int pivot = partition(arr, low, high); // 将数组分为两部分
        qsort(arr, low, pivot - 1); // 递归排序左子数组
        qsort(arr, pivot + 1, high); // 递归排序右子数组
    }
}
private static int partition(int[] arr, int low, int high) {
    int pivot = arr[low]; // 枢轴记录
    while (low < high) {
        while (low < high && arr[high] >= pivot)
            --high;
        arr[low] = arr[high]; // 交换比枢轴小的记录到左端
        while (low < high && arr[low] <= pivot)
            ++low;
        arr[high] = arr[low]; // 交换比枢轴小的记录到右端
    }
    // 扫描完成，枢轴到位
    arr[low] = pivot;
    // 返回的是枢轴的位置
    return low;
}

作者 夏目
2016 年 12月 05日

叔叔，阿姨给点钱买棒棒糖吃