🍀排序算法-平均时间复杂度
| 排序算法 | 平均时间复杂度 | 稳定性 |
|---|---|---|
| 冒泡排序 | $O(n^2)$ | 稳定排序 |
| 选择排序 | $O(n^2)$ | 非稳定排序 |
| 插入排序 | $O(n^2)$ | 稳定排序 |
| 希尔排序 | $O(n^{1.5})$ | 非稳定排序 |
| 归并排序 | $O(n*logN)$ | 稳定排序 |
| 堆排序 | $O(n*logN)$ | 非稳定排序 |
| 快速排序 | $O(n*logN)$ | 非稳定排序 |
| 计数排序 | $O(n+k)$ | 稳定排序 |
| 基数排序 | $O(n+k))$ | 稳定排序 |
| 桶排序 | $O(n+k)$ | 稳定排序 |
🍀 $O(n^2)$的排序算法
☘️冒泡排序
两个数比较大小，如要求是升序排序，则较大的数往下沉，较小的数往上冒。
伪代码
BubbleSort(A)
for i = 1 to A.length-1
for j = A.length-1 downto i
if A[j] < A[j - 1]
exchange A[j] with A[j - 1]Java版
public int[] BubbleSort(int[] list) {
int len = list.length;
for (int i = 1; i < len; i++) {
for (int j = len - 1; j >= i; j--) {
if(list[j] < list[j-1]) {
int tmp = list[j];
list[j] = list[j-1];
list[j-1] = tmp;
}
}
}
return list;
}Java泛型版
public <T extends Comparable<T>> T[] BubbleSort(T list[]) {
int len = list.length;
for (int i = 1; i < len; i++) {
for (int j = len - 1; j >= i; j--) {
if (list[j].compareTo(list[j - 1]) > 0) {
T tmp = list[j];
list[j] = list[j - 1];
list[j - 1] = tmp;
}
}
}
return list;
}**1、时间复杂度：$O(n^2)$
2、空间复杂度：$O(1)$
3、稳定排序
4、原地排序**
☘️选择排序
每次选择最小或者最大的元素排列到有序区。
*在长度为N的无序数组中，第一次遍历n-1个数，找到最小的数值与第一个元素交换；
第二次遍历n-2个数，找到最小的数值与第二个元素交换；
重复。。。
第n-1次遍历，找到最小的数值与第n-1个元素交换，排序完成。*
伪代码
SelectionSort(A)
for i=1 to A.length-1
min=i
for j=i+1 to A.length
if A[j]<A[min]
min=j
tem=A[min]
A[min]=A[i]
A[i]=temJava版
public int[] SelectionSort(int[] list) {
int len = list.length, minT;
for (int i = 0; i < len; i++) {
minT = i;
for (int j = i + 1; j < len; j++) {
if (list[j] <list[minT]) {
minT = i;
}
}
int tmp = list[minT];
list[minT] = list[i];
list[i] = tmp;
}
return list;
}Java泛型版
public <T extends Comparable<T>> T[] SelectionSort(T[] list) {
int len = list.length, minT;
for (int i = 0; i < len; i++) {
minT = i;
for (int j = i + 1; j < len; j++) {
if (list[j].compareTo(list[minT]) < 0) {
minT = i;
}
}
T tmp = list[minT];
list[minT] = list[i];
list[i] = tmp;
}
return list;
}**1、时间复杂度：$O(n^2)$
2、空间复杂度：$O(1)$
3、非稳定排序
4、原地排序**
☘️插入排序
在要排序的一组数中，假定前n-1个数已经排好序，现在将第n个数插到前面的有序数列中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。
伪代码
InsertionSort(A)
for j = 2 to A.length
key = A[j]
i = j-1
while i > 0 and A[i] > key
A[i+1] = A[i]
i = i -1
A[i+1] = keyJava代码
public int[] InsertionSort(int list[]) {
int len = list.length;
for (int i = 1; i < len; i++) {
int tmp = list[i];
int j = i - 1;
// 将比插入元素值大的数往后移动
while (j >= 0 && list[j] > tmp) {
list[j + 1] = list[j];
j--;
}
// 插入元素
list[j + 1] = tmp;
}
return list;
}Java泛型版
public <T extends Comparable<T>> T[] InsertionSort(T list[]) {
int len = list.length;
for (int i = 1; i < len; i++) {
T tmp = list[i];
int j = i - 1;
// 将比插入元素值大的数往后移动
while (j >= 0 && list[j].compareTo(tmp) > 0) {
list[j + 1] = list[j];
j--;
}
// 插入元素
list[j + 1] = tmp;
}
return list;
}**1、时间复杂度：$O(n^2)$
2、空间复杂度：$O(1)$
3、稳定排序
4、原地排序**
🍀 $O(n*logN)$的排序算法
☘️希尔排序
*在要排序的一组数中，根据某一增量分为若干子序列，并对子序列分别进行插入排序。
然后逐渐将增量减小,并重复上述过程。直至增量为1,此时数据序列基本有序,最后进行插入排序。*
假如待排序数组基本有序，使用插入排序更有效。
伪代码
ShellSort(A)
for path=0 to length_dlta
for i=path to n //一趟分段直接插入排序
temp = data[i]
j=i-path
while j>=0 and temp<data[j]
data[j+path]=data[j]
j-=path
data[j+path]=tempJava代码
private int[] ShellSort(int[] arr) {
int len = arr.length;
for (int d = len / 2;d>0;d /= 2){ //d：增量
for (int i = d; i < len; i++){
//i:代表即将插入的元素角标，作为每一组比较数据的最后一个元素角标
//j:代表与i同一组的数组元素角标
for (int j = i-d; j>=0; j-=d){ //在此处-d 为了避免下面数组角标越界
if (arr[j] > arr[j + d]) {// j+d 代表即将插入的元素所在的角标
//符合条件，插入元素（交换位置）
int temp = arr[j];
arr[j] = arr[j + d];
arr[j + d] = temp;
}
}
}
}
return arr;
}**1、时间复杂度：$O(nlogN)$ - $O(n^2)$，平均为$O(n^{1.5})$
2、空间复杂度：O(1)
3、非稳定排序
4、原地排序**
☘️归并排序
归并算法是分治思想一个经典应用。
将大的数组一直分割，直到数组的大小为 1，此时只有一个元素，那么该数组就是有序的了，之后再把两个数组大小为1的合并成一个大小为2的，再把两个大小为2的合并成4的 ….. 直到全部小的数组合并起来。
归并排序的分治思想
- 分解：分解待排序的n个元素的序列成各具 n/2 个元素的子序列
- 解决：使用归并排序递归地排序子序列
- 合并：合并两个已经排序的子序列以产生已排序的答案。
伪代码
Merge(A, p, q, r)
n1 = q-p+1
n2 = r-q
//let L[1....n1+1] and R[1....n2+1] be new arrays
for i =1 to n1
L[i] = A[p+i-1]
for j=1 to n2
R[j] = A[q+j]
L[n1+1] = ∞
L[n2+1] = ∞
i=1
j=1
for k =p to r
if L[i]<=R[j]
A[k] = L[i]
i = i + 1
else
A[k]=R[j]
j = j+1
MergeSort(A,p,r)
if p < r
q = ⌊(p+r)/2⌋ //向下取整
MergeSort(A, p, q)
MergeSort(A, q+1, r)
Merge(A, p, q, r)Java代码
public int[] MergeSort(int list[]) {
int tmp[] = new int[list.length]; //在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
MergeSort(list, 0, list.length - 1, tmp);
return list;
}
public void MergeSort(int[] list, int l, int r, int tmp[]) {
if (l < r) {
int mid = (l + r) / 2;
MergeSort(list, l, mid, tmp);
MergeSort(list, mid + 1, r, tmp);
Merge(list, l, mid, r, tmp);
}
}
void Merge(int list[], int l, int mid, int r, int tmp[]) {
int i = l; //左序列指针
int j = mid + 1; //右序列指针
int t = 0; //临时数组指针
while (i <= mid && j <= r) {
if (list[i] <= list[j]) {
tmp[t++] = list[i++];
} else {
tmp[t++] = list[j++];
}
}
while (i <= mid) { //将左边剩余元素填充进temp中
tmp[t++] = list[i++];
}
while (j <= r) { //将右序列剩余元素填充进temp中
tmp[t++] = list[j++];
}
t = 0;
//将temp中的元素全部拷贝到原数组中
while (l <= r) {
list[l++] = tmp[t++];
}
}**1、时间复杂度：$O(nlogN)$
2、空间复杂度：$O(n)$
3、稳定排序
4、非原地排序**
☘️堆排序
堆的特点就是堆顶的元素是一个最值，大顶堆的堆顶是最大值，小顶堆则是最小值。
*建立大顶堆；
拿掉堆顶的元素，重新构建堆；
拿掉堆顶元素，重新构建堆。。。
等到堆剩余的元素只有一个的时候，此时的数组就是有序的了。*
伪代码
HeapSort(A)
BuildMaxHeap(A)
for i = A.length downto 2
exchange A[1] with A[i]
A.heap-size = A.heap-size - 1
MaxHeapify(A, 1)
// 建立大顶堆
BuildMaxHeap(A)
A.heap-size = A.length
for i = int(A.length / 2) downto 1
MaxHeapify(A, i)
//维护堆
MaxHeapify(A, i)
l = LEFT(i)
r = RIGHT(i)
if l <= A.heap-size and A[l] > A[i]
largest = l
else largest = i
if r <= A.heap-size and A[r] > A[largest]
largest = r
if largest <> i
exchange A[i] with A[largest]
MaxHeapify(A, largest)Java代码
public int[] HeapSort(int list[]) {
BuildMaxHeap(list);
for (int i = list.length - 1; i >= 0; i--) {
int tmp = list[0];
list[0] = list[i];
list[i] = tmp;
MaxHeapify(list, 0, i);
}
return list;
}
public void BuildMaxHeap(int list[]) {
// 构建大顶堆
int heapSize = list.length;
for (int i = (heapSize / 2); i >= 0; i--) {
MaxHeapify(list, i, heapSize);
}
}
public void MaxHeapify(int list[], int i, int heapSize) {
// 维护堆
int l = LEFT(i);
int r = RIGHT(i);
int largest;
if (l <= heapSize - 1 && list[l] > list[i]) {
largest = l;
} else {
largest = i;
}
if (r <= heapSize - 1 && list[r] > list[largest]) {
largest = r;
}
if (largest != i) {
int tmp = list[i];
list[i] = list[largest];
list[largest] = tmp;
MaxHeapify(list, largest, heapSize);
}
}
public int PARENT(int i) {
return (i - 1) / 2;
}
public int LEFT(int i) {
return 2 * i + 1;
}
public int RIGHT(int i) {
return 2 * i + 2;
}**1、时间复杂度：$O(nlogN)$
2、空间复杂度：$O(1)$
3、非稳定排序
4、原地排序**
☘️快速排序
同样是分治思想。
*先从数列中取出一个数作为key值；
将比这个数小的数全部放在它的左边，大于或等于它的数全部放在它的右边；
对左右两个小数列重复第二步，直至各区间只有1个数。*
伪代码
QuickSort(A, p, r)
if p < r
q = Partition(A,p,r）
QuickSort(A,p,q-1)
QuickSort(A,q+1,r)
Partition(A, p, r)
x = A[r]
i = p-1
for j = p to r-1
if A[j] <= x
i = i + 1
exchange A[i] with A[j]
exchange A[i+1] with A[r]
return i + 1Java代码
public int[] QuickSort(int list[]) {
QuickSort(list, 0, list.length - 1);
return list;
}
public void QuickSort(int list[], int l, int r) {
if (l < r) {
int mid = Partition(list, l, r);
QuickSort(list, l, mid - 1);
QuickSort(list, mid + 1, r);
}
}
public int Partition(int list[], int l, int r) {
int x = list[r];
int i = l - 1;
for (int j = l; j <= r - 1; j++) {
if (list[j] <= x) {
i = i + 1;
int tmp = list[i];
list[i] = list[j];
list[j] = tmp;
}
}
int tmp = list[i + 1];
list[i + 1] = list[r];
list[r] = tmp;
return i + 1;
}**1、时间复杂度：$O(nlogN)$
2、空间复杂度：$O(logN)$
3、非稳定排序
4、原地排序**
🍀$O(n+k)$的排序算法、非比较排序
☘️计数排序
把数组元素作为数组的下标，然后用一个临时数组统计该元素出现的次数，例如 temp[i] = n, 表示元素 i 一共出现了 n 次。最后再把临时数组统计的数据从小到大汇总起来，此时汇总起来是数据是有序的。
计数排序比较适用于待排序数组中最大值和最小值相差不大的排序。
伪代码
CountingSort(A,B,k)
let C[0..k] be a new array
for i = 0 to k //后面需要使用数组C来存储A中各元素的出现次数，所以需要清零操作
C[i] = 0
for j = 1 to A.length
C[A[j]] = C[A[j]] + 1 //统计A中各元素的出现次数存储在C中，C中下标为A中的元素值，与其对应的数组元素为出现次数，如C[1] = 0，即为“1”在A中的出现次数为0
for i = 1 to k
C[i] = C[i] + C[i-1] //计算A中小于等于i的一共有多少个，方便此后将i放在数组B中正确的位置上
for j = A.length downto 1
B[C[A[j]]] = A[j] //使用A中元素A[j]的出现次数作为B中的下标，把每个元素放在B中适当的位置
C[A[j]] = C[A[j]] -1 //在B中放入一个元素，与其对应C中出现的次数-1。这样，当遇到下一个等于A[j]的输入元素时，该元素可以被直接放到B中A[j]的前一位置上Java代码
public int[] CountingSort(int list[]) {
int maxNum = Arrays.stream(list).max().getAsInt();
CountingSort(list, maxNum);
return list;
}
public void CountingSort(int list[], int maxNum) {
int tmp[] = new int[maxNum + 1];
int res[] = new int[list.length];
for (int item : list) {
tmp[item]++;
}
for (int i = 1; i < tmp.length; i++) {
tmp[i] += tmp[i - 1];
}
for (int i = list.length - 1; i >= 0; i--) {
// 数组下标从0开始，此处减1
res[tmp[list[i]]-1] = list[i];
tmp[list[i]]--;
}
}**1、时间复杂度：$O(n+k)$ ，K：建立的计数数组长度
2、空间复杂度：$O(n+k)$
3、稳定排序
4、非原地排序**
☘️基数排序
*先以个位数的大小来对数据进行排序，接着以十位数的大小来多数进行排序，接着以百位数的大小。。。
排到最后，就是一组有序的元素了。*
伪代码
RADIXSORT(A,d) // d:最高位数
for i = 1 to d
use a stable sort to sort array A on digit i // 从个位数至高位数依次重复排序Java代码
public int[] RadixSort(int list[]) {
int maxNum = Arrays.stream(list).max().getAsInt();
int d = 0;
while(maxNum!=0) {
maxNum /=10;
d++;
}
RadixSort(list,d);
return list;
}
public void RadixSort(int list[], int d) {
int[] res = new int[list.length];//结果数组
int[] tmp = new int[10];//计数数组，范围为每位上的取值范围0-9
//一个十进制数m，它的个位数是m/1%10，十位数是m/10%10,百位数是m/100%10
for(int i=0;i<d;i++) {
int division = (int)Math.pow(10, i);//取个位::/1 十位:/10 百位:/100中的基本划分点
for(int j=0;j<list.length;j++) {
int num = list[j]/division%10;//取个位 十位 或百位上的数，每轮由此位置上的数大小进行计数排序
tmp[num]=tmp[num]+1;//进行计数排序中计数数组的更新
}
//计数排序中计数数组count的累加，保证稳定性
for(int m=1;m<tmp.length;m++) {
tmp[m]=tmp[m]+tmp[m-1];
}
//计数排序中逆序遍历原数组A，根据累加后的数组count将A中每个元素正确填入result中正确的位置中
for(int j=list.length-1;j>=0;j--) {
int num = list[j]/division%10;
res[tmp[num]-1]=list[j];
tmp[num]=tmp[num]-1;
}
//将数组A更新为数组B
for(int j=0;j<list.length;j++) {
list[j]=res[j];
}
//将数组C清零，进行下一轮的循环
for(int j=0;j<tmp.length;j++) {
tmp[j]=0;
}
}
}**1、时间复杂度：$O(n+k)$ ，K：建立的计数数组长度
2、空间复杂度：$O(n+k)$
3、稳定排序
4、非原地排序**
☘️桶排序
把最大值和最小值之间的数进行瓜分，例如分成 10 个区间，10个区间对应10个桶，我们把各元素放到对应区间的桶中去，再对每个桶中的数进行排序，对桶中元素排序可采用其他排序方法。每个桶排序后再合并起来形成有序数组。
伪代码
BucketSort(A)
n = A.length
let B[0...n-1] be a new array
for i = 0 to n-1
b[i]=0
//make B an empty list
for i =1 to n
insert A[i] into list B[(int)nA[i]]
for i =0 to n-1
sort list B[i] with insertion sort
concatenate hte lists B[0...n-1] together in orderJava代码
class LinkedNode {
public int value;
public LinkedNode next;
public LinkedNode(int value) {
this.value = value;
}
}
public int[] BucketSort(int list[]) {
int length = list.length;
LinkedNode[] bucket = new LinkedNode[length]; // 桶的个数等于length
int max = list[0]; // 求max
for (int i = 1; i < list.length; i++) {
if (list[i] > max) {
max = list[i];
}
}
// 入桶
for (int i = 0; i < length; i++) {
int value = list[i]; // 扫描每个元素
int hash = hash(list[i], max, length); // 桶的下标
if (bucket[hash] == null) {
bucket[hash] = new LinkedNode(value); // 初始化链表
} else {
insertInto(value, bucket[hash], bucket, hash); // 插入链表
}
}
int k = 0; // 记录数组下标
// 出桶，回填arr
for (LinkedNode node : bucket) {
if (node != null) {
while (node != null) {
list[k++] = node.value;
node = node.next;
}
}
}
return list;
}
private int hash(int element, int max, int length) {
return (element * length) / (max + 1);
}
private void insertInto(int value, LinkedNode head, LinkedNode[] bucket, int hash) {
LinkedNode newNode = new LinkedNode(value);
// 小于头节点，放在头上
if (value <= head.value) {
newNode.next = head;
// 替换头节点
bucket[hash] = newNode;
return;
}
// 往后找第一个比当前值大的节点，放在这个节点的前面
LinkedNode p = head;
LinkedNode pre = p;
while (p != null && value > p.value) {
pre = p;
p = p.next;
}
if (p == null) { // 跑到末尾了
pre.next = newNode;
} else { // 插入pre和p之间
pre.next = newNode;
newNode.next = p;
}
}**1、时间复杂度：$O(n+k)$ ，K：建立的计数数组长度
2、空间复杂度：$O(n+k)$
3、稳定排序
4、非原地排序**
