Open jeasonstudio opened 6 years ago
下面主要写了数据结构课本上介绍的「十种排序算法」,趁着快考试了复习一波排序,有图有真相,看不懂打死我吧。
堆排序、快速排序、希尔排序、直接选择排序不是稳定的排序算法,而基数排序、冒泡排序、直接插入排序、折半插入排序、链表插入排序、归并排序是稳定的排序算法。
直接插入排序 T(n) = O(n^2)
直接插入排序「Insertion Sort」的基本思想是:每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子序列中的适当位置,直到全部记录插入完成为止。
设数组为a[0…n-1]:
折半插入排序 T(n) = O(n^2)
折半插入排序是对直接插入排序的简单改进,对于折半插入排序而言,当需要插入第i个元素时,它不会逐个进行比较每个元素,而是:
链表插入排序 T(n) = O(n^2)
链表插入排序的基本思想是:假设前 n-1个节点有序,取最后节点,沿链表依次查找比较,直到合适位置,修改「本节点」和「待插入节点」的指针。
Shell 排序(希尔排序) T(n) = O(n^1.5)
希尔排序的实质就是分组插入排序,该方法又称缩小增量排序。该方法的基本思想是:
冒泡排序 T(n) = O(n^2)
冒泡排序的基本思想是,对相邻的元素进行两两比较,顺序相反则进行交换,这样,每一趟会将最小或最大的元素“浮”到顶端,最终达到完全有序。
快速排序 范围T(n) = O(nlg n) ~ O(n^2) | 平均T(n) = O(nlg n)
快速排序采用了分治(递归)的方法,该方法的基本思想是:
直接选择排序 T(n) = O(n^2)
直接选择排序(Straight Select Sorting) 也是一种简单的排序方法,它的基本思想是:
堆选择排序 T(n) = O(n*log2n)
堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。堆分为大根堆和小根堆,下图为小根堆:
「如图所示依次类推」
归并排序 T(n) = O(n*log2n)
归并排序是建立在归并操作上的一种有效的排序算法,采用了分治思想。如下图的二路归并:
基数排序
基数排序(radix sort)属于「分配式排序」,有点类似 「桶排」。
数据结构与算法之排序—看不懂你来打我吧
下面主要写了数据结构课本上介绍的「十种排序算法」,趁着快考试了复习一波排序,有图有真相,看不懂打死我吧。
堆排序、快速排序、希尔排序、直接选择排序不是稳定的排序算法,而基数排序、冒泡排序、直接插入排序、折半插入排序、链表插入排序、归并排序是稳定的排序算法。
直接插入排序「Insertion Sort」的基本思想是:每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子序列中的适当位置,直到全部记录插入完成为止。
设数组为a[0…n-1]:
折半插入排序是对直接插入排序的简单改进,对于折半插入排序而言,当需要插入第i个元素时,它不会逐个进行比较每个元素,而是:
链表插入排序的基本思想是:假设前 n-1个节点有序,取最后节点,沿链表依次查找比较,直到合适位置,修改「本节点」和「待插入节点」的指针。
希尔排序的实质就是分组插入排序,该方法又称缩小增量排序。该方法的基本思想是:
冒泡排序的基本思想是,对相邻的元素进行两两比较,顺序相反则进行交换,这样,每一趟会将最小或最大的元素“浮”到顶端,最终达到完全有序。
快速排序采用了分治(递归)的方法,该方法的基本思想是:
直接选择排序(Straight Select Sorting) 也是一种简单的排序方法,它的基本思想是:
堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。堆分为大根堆和小根堆,下图为小根堆:
「如图所示依次类推」
归并排序是建立在归并操作上的一种有效的排序算法,采用了分治思想。如下图的二路归并:
基数排序(radix sort)属于「分配式排序」,有点类似 「桶排」。