数据结构与算法-排序(上)

Posted on | Edited on | In ,

如何选择一种排序算法

算法的执行效率

  • 最好、最坏、平均时间复杂度：需要根据要排序数据的大小、以及是否接近有序来考虑时间复杂度。
  • 考虑时间复杂度的系数、常量、低阶：对于通一时间复杂度的数据要考虑这些。
  • 比较次数和交换次数：基于比较的排序涉及到数据的交换所以要考虑比较次数和交换次数。

算法的内存消耗

原地排序指空间复杂度是O(1)的排序，我们在选择的时候也要针对硬件考虑算法的空间复杂度

算法的稳定性

指如果数据有俩个相等的元素，当排序后者俩个相等元素之间的顺序没发生改变，我们管他叫稳定的排序。相反则是不稳定的排序。

算法稳定性的意义以及用法，对于一个对象按照俩个属性维度排序。如：对于一个账户的金额排序，金额相等的按照时间倒序。

  1. 我们可以先按照时间倒叙排序，得到时间倒叙排序的列表；

  2. 用稳定性排序算法按照金额大小进行排序，由于是稳定性的排序算法所以金额相等的数据原有顺序不变依然是时间倒叙。

    规律：先按照第二个属性排序（即xx相等，按照xx排序），在按照第一个属性排序。

算法的有序度和逆序度

一个数组中，有顺序的元素个数较为有序度。相反，则成为逆序度。一个完全有序的数据我们称他为满有序度。公式是：逆序度=满有序度-有序度。
排序实际上是减少逆序度最终达到满有序度的过程

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class BubbleSort {

    public int[] sort(int[] array) {
        //第一层循环没循环一次冒泡一次，如果某一次没有发生位置变化说明数组已经完全有序，停止冒泡needBuuble
        for (int i = 0; i < array.length; i++) {
            boolean needBuuble=false;
            for (int j = i + 1; j < array.length-i; j++) {
                int tmp = array[j];
                if (array[i] > array[j]) {
                    array[j] = array[i];
                    array[i] = tmp;
                    needBuuble=true;
                }
            }
            if(!needBuuble){
                return array;
            }
        }
        return array;
    }
}

算法分析

时间复杂度：最好的情况是数组完全有序，只做一次循环就退出。最坏的时间复杂度是O(n*n),完全倒序需要都交换一次。

空间复杂度：相邻俩个元素比较交换，没有用到额外的空间属于O(1)

算法稳定性：俩个元素相同，不交换位置所以是算法稳定。

注：如果不优化，时间复杂度就是O(n*n).

选择排序

选择排序，循环数组，每次都找到数组最小值，然后和当前元素互换位置，知道结束，

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
public class SelectionSorts {

    /**
     * 选择排序，循环数组，每次都找到数组最小值，然后和当前元素互换位置，知道结束，
     * 时间负责度最好O(n*n)，最坏O(n*n)，平均都是O(n*n)，且不稳定
     * @param a
     * @return
     */
    public int[] sort(int[] a) {
        for (int i = 0; i < a.length; i++) {

            //记录最小值和索引
            int min=a[i];
            int minIdx=i;

            //循环查找最小值
            for(int j=i+1;j<a.length;j++){
                if(a[j]<min){
                    min=a[j];
                    minIdx=j;
                }
            }

            //如果当前值不是最小值，最小值和当前值互换位置
            if(i!=minIdx){
                int tmp=a[minIdx];
                a[minIdx]=a[i];
                a[i]=tmp;
            }
        }

        return a;
    }

}

选择排序-算法分析

时间复杂度：时间负责度最好O(nn)，最坏O(nn)，平均都是O(n*n)

空间复杂度：没有用到额外的空间属于O(1)

算法稳定性：不稳定每次都要交换位置，如果值相等也可能在交换后改变顺序

归并排序

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
public void sort(int a[], int start, int end) {
       if (start >= end) {
           return;
       }

       //利用分治思想递归
       int mid = (start + end) / 2;
       sort(a, start, mid);
       sort(a, mid + 1, end);

       merge(a, start, mid, end);
   }

   private void merge(int[] a, int start, int mid, int end) {
       //临时数组等于a里start-->end
       int[] tmp = new int[end - start + 1];//注意：一定是end-start+1，因为这是Index,长度要+1（0--2长度是3）
       int k = 0;

       //给tmp赋值，逻辑是i从start-->mid，j从mid+1-->end
       int i = start;
       int j = mid + 1;
       while (i <= mid && j <= end) {
           tmp[k++] = a[i] < a[j] ? a[i++] : a[j++];
       }

       //剩余补进临时数组
       while (i <= mid) {
           tmp[k++] = a[i++];
       }
       while (j <= end) {
           tmp[k++] = a[j++];
       }

       //将临时数据写入到a中
       for (int x = 0; x < tmp.length; x++) {
           a[start + x] = tmp[x];
       }
   }

归并排序 算法分析

时间复杂度：时间负责度最好O(nlogn)，最坏O(nnlogn)，平均都是O(nnlogn)

空间复杂度：每次merge都需要开辟一块空间但是每次都释放掉，空间复杂度就是O(n)

算法稳定性：稳定

快速排序

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
/**
 * 获取数组的一个标志位（交换区点一般是数组最后一位，小于这个点的在左边，大于的在右边）
 *
 * @param a
 * @param s
 * @param e
 */
private void sort(int[] a, int s, int e) {
    if (s >= e) {
        return;
    }

    int poivt = poivt(a, s, e);
    sort(a, s, poivt - 1);//排序取到分区点后，分区点-1，参与排序
    sort(a, poivt, e);//从分区点到终点排序
}

private int poivt(int[] a, int s, int e) {
    int swapIdx = s;//交换区为s，随着数组循环移动
    int flag = a[e];//设置flag即最后交换区

    //s-->e-1,循环到交换区前
    for (int i = s; i <= e - 1; i++) {
        //即时小于也要交换，让swpIdx后移
        if (a[i] <= flag) {
            int tmp = a[i];
            a[i] = a[swapIdx];
            a[swapIdx] = tmp;
            swapIdx++;//扩大前半部分
        }
    }

    //最后将flag移动到此次poivt点并且返回交换区点
    int tmp = a[swapIdx];
    a[swapIdx] = flag;
    a[e] = tmp;

    return swapIdx;
}

快排复杂度分析