5、排序

一、排序方法与复杂度归类
(1)几种最经典、最常用的排序方法:冒泡排序、插入排序、选择排序、快速排序、归并排序、计数排序、基数排序、桶排序。
(2)复杂度归类
冒泡排序、插入排序、选择排序 O(n^2)
快速排序、归并排序 O(nlogn)
计数排序、基数排序、桶排序 O(n)

二、如何分析一个“排序算法”?
<1>算法的执行效率

  1. 最好、最坏、平均情况时间复杂度。
  2. 时间复杂度的系数、常数和低阶。
  3. 比较次数,交换(或移动)次数。
    <2>排序算法的稳定性
  4. 稳定性概念:如果待排序的序列中存在值相等的元素,经过排序之后,相等元素之间原有的先后顺序不变。
  5. 稳定性重要性:可针对对象的多种属性进行有优先级的排序。
  6. 举例:给电商交易系统中的“订单”排序,按照金额大小对订单数据排序,对于相同金额的订单以下单时间早晚排序。用稳定排序算法可简洁地解决。先按照下单时间给订单排序,排序完成后用稳定排序算法按照订单金额重新排序。
    <3>排序算法的内存损耗
    原地排序算法:特指空间复杂度是O(1)的排序算法。
常见的排序算法:

冒泡排序

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较,看是否满足大小关系要求,如果不满足就让它俩互换。

代码:

public int[] bubbleSort(int[] a) {
int n = a.length;
if (n<=1) {
return a;
}
for (int i = 0; i < n; i++) {
//提前退出冒泡循环的标志
boolean flag = false;
for (int j = 0; j < n-i-1; j++) {
if (a[j]>a[j+1]) {//
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;

                flag = true;//表示有数据交换
            }
            if (!flag) {
                break; //没有数据交换(说明已排好序无需再进行冒泡),提前退出
            }
        }
    }
    return a;
}
四、插入排序

插入排序将数组数据分成已排序区间和未排序区间。初始已排序区间只有一个元素,即数组第一个元素。在未排序区间取出一个元素插入到已排序区间的合适位置,直到未排序区间为空。

代码:

public int[] insertionSort(int[] a) {
    int n = a.length;
    if (n<=1) return a;

    for (int i = 1; i < n; i++) {
        int value = a[i];
        int j = i-1;
        for (; j >=0; j--) {
            if (a[j] > value) {
                a[j+1] = a[j];//移动数据
            }else {
                break;
            }
        }
        a[j+1] = value;//插入数据
    }

    return a;
}
五、选择排序

选择排序将数组分成已排序区间和未排序区间。初始已排序区间为空。每次从未排序区间中选出最小的元素插入已排序区间的末尾,直到未排序区间为空。
代码:

public int[] selectionSort(int[] a) {
int n = a.length;

    for (int i = 0; i < a.length - 1; i++) {
        for (int j = i+1; j < a.length; j++) {
            //交换
            if (a[i] > a[j]) {
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
    }

    return a;
}
六、归并排序

如果要排序一个数组,我们先把数组从中间分成前后两部分,然后对前后两部分分别排序,再将排好序的两部分合并在一起,这样整个数组就都有序了。

实现思路:

merge-sort(p...r)表示,给下标从p到r之间的数组排序。我们将这个排序问题转化为了两个子问 ,题, merge_sort(p...q)和merge-sort(q+1..r),其中下标q等于p和r的中间位置,也就是, (p+r)/2,当下标从p到q和从q+1到r这两个子数组都排好序之后,我们再将两个有序的子数组合并在一起,这样下标从p到r之间的数据就也排好序了。

代码:

// 归并排序算法, a是数组,n表示数组大小
public static void mergeSort(int[] a, int n) {
mergeSortInternally(a, 0, n-1);
}

// 递归调用函数
private static void mergeSortInternally(int[] a, int p, int r) {
// 递归终止条件
if (p >= r) return;

// 取p到r之间的中间位置q
int q = (p+r)/2;
// 分治递归
mergeSortInternally(a, p, q);
mergeSortInternally(a, q+1, r);

// 将A[p...q]和A[q+1...r]合并为A[p...r]
merge(a, p, q, r);

}

private static void merge(int[] a, int p, int q, int r) {
int i = p;
int j = q+1;
int k = 0; // 初始化变量i, j, k
int[] tmp = new int[r-p+1]; // 申请一个大小跟a[p...r]一样的临时数组

// 1 排序
while (i<=q && j<=r) {
  if (a[i] <= a[j]) {
    tmp[k++] = a[i++]; // i++等于i:=i+1
  } else {
    tmp[k++] = a[j++];
  }
}

// 2 判断哪个子数组中有剩余的数据
int start = i;
int end = q;
if (j <= r) {
  start = j;
  end = r;
}

// 3 将剩余的数据拷贝到临时数组tmp
while (start <= end) {
  tmp[k++] = a[start++];
}

// 4 将tmp中的数组拷贝回a[p...r]
for (i = 0; i <= r-p; ++i) {
  a[p+i] = tmp[i];
}

}

merge是这样执行的:

代码分析:


七、快速排序

快排的思想: 如果要排序数组中下标从p到r之间的一组数据,我们选择p到r之间的任意一个数据作为pivot (分区点) 。我们遍历p到r之间的数据,将小于pivot的放到左边,将大于pivot的放到右边,将pivot放到中间。经过这一步骤之后,数组p到r之间的数据就被分成了三个部分,前面p到q-1之间都是小于pivot的,中间是pivot,后面的q+1到r之间是大于pivot的。

快排利用的分而治之的思想

八、线性排序:
时间复杂度O(n)

我们把时间复杂度是线性的排序算法叫作线性排序(Linear sort)常见的线性算法有: 桶排序、计数排序、基数排序

特点:

非基于比较的排序算法

桶排序

桶排序,顾名思义,会用到“桶" ,核心思想是将要排序的数据分到几个有序的桶里,每个桶里的数据再单独进行排序。桶内排完序之后,再把每个桶里的数据按照顺序依次取出,组成的序列就是有序的了。

对排序的数据要求苛刻:

1, 要排序的数据需要很容易就能划分成m个桶,并且,桶与桶之间有着天然的大小顺序。

2 ,数据在各个桶之间的分布是比较均匀的。

3 ,桶排序比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中,数据量比较大,内存有限,无法将数据全部加载到内存中。

计数排序

计数排序只能用在数据范围不大的场景中,如果数据范围k比要排序的数据n大很多,就不适合用计数排序了。

计数排序只能给非负整数排序,如果要排序的数据是其他类型的,要将其在不改变相对大小的情况下,转化为非负整数。

代码:

// 计数排序,a是数组,n是数组大小。假设数组中存储的都是非负整数。
public static void countingSort(int[] a) {
int n = a.length;
if (n <= 1) return;

// 查找数组中数据的范围
int max = a[0];
for (int i = 1; i < n; ++i) {
  if (max < a[i]) {
    max = a[i];
  }
}

// 申请一个计数数组c,下标大小[0,max]
int[] c = new int[max + 1];
for (int i = 0; i < max + 1; ++i) {
  c[i] = 0;
}

// 计算每个元素的个数,放入c中
for (int i = 0; i < n; ++i) {
  c[a[i]]++;
}

// 依次累加
for (int i = 1; i < max + 1; ++i) {
  c[i] = c[i-1] + c[i];
}

// 临时数组r,存储排序之后的结果
int[] r = new int[n];
// 计算排序的关键步骤了,有点难理解
for (int i = n - 1; i >= 0; --i) {
  int index = c[a[i]]-1;
  r[index] = a[i];
  c[a[i]]--;
}

// 将结果拷贝会a数组
for (int i = 0; i < n; ++i) {
  a[i] = r[i];
}
}



散列表
什么是散列表:
散列表用的是数组支持按照下标随机访问数据的特性,所以散列表其实就是数组的一种扩展,由数组演化而来。可以说,如果没有数组,就没有散列表。

原理:
散列表用的就是数组支持按照下标随机访问的时候,时间复杂度是0(1)的特性。我们通过散列函数把元素的键值映射为下标,然后将数据存储在数组中对应下标的位置。当我们按照键值查询元素时,我们用同样的散列函数,将键值转化数组标标,从对应的数组下标的位置取数据。

散列函数的设计要求:
散列函数计算得到的散列值是一个非负整数;.
如果key1 = key2,那hash(key1) == hash(key2);
如果key1 != key2,那hash(key1)  !=  hash(key2),
散列函数的设计不能太复杂,散列函数生成值要尽可能随机并且均匀分布

如果不符合3 那么就出现了散列冲突,散列冲突是无法避免的

解决散列冲突的方法有两种: 
开放寻址法(open addressing)和链表法(chaining)

开放寻址法:如果出现了散列冲突,我们就重新探测一个空闲位置,将其插入。

装在因子:  散列表中一定比例的空闲槽位。公式: 散列表的装载因子 = 填入表中的元素个数 / 散列表的长度

装载因子越大,说明空闲位置越少,冲突越多,散列表的性能会下降。

链表法:

链表法是一种更加常用的散列冲突解决办法,相比开放寻址法,它要简单很多。我们来看这个图,在散列表中,每个"桶(bucket) "或者"槽(slot) "会对应一条链表,所有散列值相同的元素我们都放到相同槽位对应的链表中。




祝大家面试必过,了解下阿里大数据中台的实习岗位 https://www.nowcoder.com/discuss/604553