不会飞的章鱼

熟能生巧,勤能补拙;念念不忘,必有回响。

算法训练营-初级排序和高级排序的实现和特性

排序算法

1,比较类排序

通过比较来决定元素间的相对次序,由于其时间复杂度不能突破O(nlogn),因此也称为非线性时间比较类排序。

2,非比较类排序

不通过比较来决定元素间的相对次序,它可以突破基于比较排序的时间下界,以线性时间运行,因此也称为线性时间非比较类排序。

(大厂一般回考时间复杂度为nlogn的排序算法——堆排序、快速排序、归并排序,比如快速排序和归并排序用到了分治思想)

初级排序-O(n^2)

  • 1,选择排序
    每次找最小值,然后放到待排序数组的起始位置。

  • 2,插入排序
    从前往后逐步构建有序序列;对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

  • 3,冒泡排序
    嵌套循环,每次查看相邻的元素,如果逆序,则交换

高级排序-O(N*LogN)

  • 快速排序
    数组取标杆pivot,将小元素放pivot左边,大元素放右侧,然后依次对右边和右边的子数组继续快排,以达到整个序列有序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// Go
func quickSort(array []int, begin, end int) {
if end <= begin {
return
}
pivot := partition(array, begin, end)
quickSort(array, begin, pivot-1)
quickSort(array, pivot+1, end)
}

func partition(array []int, begin, end int) int {
// pivot: 标杆位置,counter: 小于pivot的元素的个数
pivot, counter := end, begin
for i := begin; i < end; i++ {
if array[i] < array[pivot] {
array[i], array[counter] = array[counter], array[i]
counter++
}
}
array[pivot], array[counter] = array[counter], array[pivot]
return counter
}
  • 归并排序——分治
    1,把长度为n的输入序列分成两个长度为n/2的子序列;
    2,把这两个子序列分别采用归并排序;
    3,将两个排序好的子序列合并成一个最终的排序序列。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//java
public static void mergeSort(int[] array,int left,int right) {
if (right <= left) return;
int mid = (left + right) >> 1; //(left + right) / 2

mergeSort(array,left,mid);
mergeSort(array,mid + 1,right);
merge(array,left,mid,right);
}

public static void merge(int[] arr,int left,int mid,int right) {
int[] temp = new int[right - left + 1]; //中间数组
//...未完
}

小结

归并和快排具有相似性,但步骤顺序相反

归并:先排序左右子数组,然后合并两个有序子数组;
快排:先调配出左右子数组,然后对于左右子数组进行排序。

  • 堆排序——堆插入O(logN),取最大/小值O(1)
    1,数组元素依次建立小顶堆;
    2,依次取堆顶元素,并删除。
1
//Cpp

链接

十大经典排序算法(动图演示)
快速排序算法示例
归并排序算法示例
堆排序代码示例

------ 本文结束------
如果本篇文章对你有帮助,可以给作者加个鸡腿~(*^__^*),感谢鼓励与支持!