-
分析问题:
- 排序算法的执行效率(最好情况,最坏情况,平均时间复杂度)
- 时间复杂度的系数,常数,低阶(平常n值很小的情况下)
- 比较次数和交换(移动)次数,尽可能少
-
排序算法的内存消耗(空间复杂度)
- 原地排序: 特指空间复杂度为O(1)的排序算法
-
排序算法的稳定性:
-
如果待排序的序列中有相同的值,经过排序以后,不改变他们之间原有的先后顺序
例如: 根据订单的金额大小跟下单时间排序,一般都是按照时间顺序储存数据表,此时根据金额排序只能使用稳定性的算法,否则相同金额的,下单时间就不是正序了;
-
- 只操作相邻的两个数据进行比较,每次都将最大或者最小的值移动到相应的位置中,重复n次就完成排序
//冒泡排序
private void bubbleSort() {
int [] arr = new int[]{1,4,3,5,2,7,9,8};
if (arr == null || arr.length == 1){
return;
}
int n = arr.length;
for (int i = 0; i < n; i++) {
boolean isChange = false ; //是否有更改的标志
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]){
int temp = arr[j + 1] ;
arr[j + 1] = arr[j];
arr[j] = temp ;
isChange = true ;
}
}
if (!isChange){ //没有数据交换,提前退出程序
break;
}
}
}
-
总结
-
冒泡排序是原地排序算法：只涉及相邻元素交换操作，空间复杂度为O(1);
-
冒泡排序是稳定的排序算法：再交换中相等的数据不交换位置，前后顺序不发生改变；
-
时间复杂度：
-
最好O(n)(上方代码i=0，j由0->n-1结束),
-
最坏情况为倒序排列O(n^2)；
-
平均时间复杂度的计算方式；
-
有序度：数组中具有有序关系的元素对的个数：a[i] < a[j] , 如果 i < j ;
如 2 ，4 ，3 有序度为（2,4）,(2.3) 有序度为2,对于倒序排列数组 4,3,2有序度为0
-
满有序度:对于完全有序的数组 2,3,4有序度为n *(n -1)/2 = 3
-
逆有序度:a[i] > a[j] ,如果 i < j ;
-
逆有序度 = 满有序度 - 有序度,我们排序的过程就是一种增加有序度,减少逆有序度最终达到满有序度就说明排序完成了;
-
-
-
-
将数组分为 已排序区间跟未排序区间:初始已排序区间只有一个元素.就是数组的第一个元素;
-
核心思想是取未排序区间中的元素,在已排序区间中找到合适的位置插入并保证已排序区间数据一致有序,重复这个过程,知道未排序区间中元素有空,算法结束;
-
插入排序有两种操作:一种是元素的比较,一种是元素的移动,找到合适的插入点,然后将插入点之后的元素顺序向后移动一位,这样才能腾出位置给元素插入;
-
对于不同的插入点方式,比较次数有区别,但是移动次数是固定的为数组的逆序度:
-
例如 4，5，6，1，3，2,满有序度为n*(n -1)/2 = 15, 当前初始序列有序度为:5,则逆序度为10;
1插入第一位移动4,5,6 ->1, 4，5，6，3，2 (3次)
3插入第二位移动4,5,6 -> 1,3,4,5,6,2 (3次)
2插入第二位移动3,4,5,6 ->1.2,3,4,5,6(4次)
插入移动次数总和为 3 + 3 + 4 = 15 - 5 = 10次
-
/**
* 插入算法
*/
private void insertSort() {
int[] arr = new int[]{1, 4, 3, 0, 5, 2, 7, 9, 8};
if (arr == null || arr.length == 1) {
return;
}
int n = arr.length;
for (int i = 1; i < n - 1; i++) {
int value = arr[i];
int j = i - 1; //需要插入的有序区间中 将数据arr[i] 插入到0->j已排序区间中
for (; j >= 0; j--) {
if (arr[j] > value) { //比较以后移动位置
arr[j + 1] = arr[j];
} else {
break;
}
}
//将数据插入到位置中,上方j的位置元素arr[j]=<value了插入它后一位 j+1
arr[j + 1] = value;
}
}
- 总结:
- 插入排序是原地算法:不需要额外的储存空间,空间复杂度为O(1);
- 插入排序是稳定的排序算法,比较的是arr[j] > value等于的时候不移动先后顺序
- 时间复杂度:
- 最好时间复杂度:如果已经有序,移动次数为0 ,只需要前后比较,每次比较都能确定插入位置,最好的时间复杂度为O(n);
- 最坏时间复杂度:如果数组是倒序的,每次插入都相当于在数组第一个位置插入新的数据,移动为n(n-1)/2,所以最坏时间复杂度为O(n^2);
- 平均时间复杂度:由于我们在数组中插入一个数据的平均时间复杂度为O(n),所以插入排序的平均复杂度为循环执行n次插入操作,所以平均时间复杂度为O(n^2)
* 也分为已排序区间和未排序区间,但是选择排序每次会从为排序区间中找到最小的元素,将其放到已排序区间的末尾
// 选择排序，a表示数组，n表示数组大小
public static void selectionSort(int[] a, int n) {
if (n <= 1) return;
for (int i = 0; i < n - 1; ++i) {
// 查找最小值的索引
int minIndex = i;
for (int j = i + 1; j < n; ++j) {
if (a[j] < a[minIndex]) {
minIndex = j;
}
}
// 交换两个数据:可以判断一下 i!= minIndex才交换数据
int tmp = a[i];
a[i] = a[minIndex];
a[minIndex] = tmp;
}
}
- 总结:
- 原地排序算法,空间复杂度为O(1)
- 稳定性:每次都要找剩余未排序元素中最小值,并和前面的元素交换位置,破坏了稳定性;
- 时间复杂度:
- 最好时间复杂度:如果数组有序,也将比较n^2次,只是不再交换位置了O(n^2)
- 最坏时间复杂度:比较n^2 + 交换n次总共还是O(n^2)
- 平均时间复杂度:根据极限规则还是O(n^2)
- 插入排序 > 冒泡排序 > 选择排序(基本不用),why?
- 冒泡排序中元素的交换次数为固定值 -> 原始数据的逆序度
- 插入排序中元素的移动次数为固定值 -> 原始数据的逆序度
- 但是冒泡排序的交换需要3次赋值操作,而插入排序只需要1次;
-
归并排序思想:排序一个数组,先将数组从中间分成前后两部分,在对前后两部分分辨排序,再将排序号的两部分合并在一起,这样整个数组就是有序的了;
-
递推公式
merge_sort(p...r) = merge(merge_sort(p...q) , merge_sort(q+1...r)); 终止条件为 p >= r 不用在继续分解- 简单的伪代码:
//归并排序算法,arr数组,n表示数组大小 merge_sort(arr , n){ merge_sort_c(arr , 0 , n -1); //从0跟n-1开始排序 } //递归调用函数 merge_sort_c(arr , p , r){ if (p >= r){ return ; //结束递归的终止条件 } //取p到r之间的中间位置q q = (p + r)/2 ; //分治递归调用 merge_sort_c(arr , p , q); //排序前面部分 merge_sort_c(arr , q , r); //排序后面部分 //将将 A[p...q] 和 A[q+1...r] 合并为 A[p...r] merge(arr[p...r] , arr[p...q] , arr[q+1...r]); }-
真实代码
public class MergeSort { // 归并排序算法, 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,防止（p+r）的和超过int类型最大值 int q = p + (r - p)/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]一样的临时数组 while (i<=q && j<=r) { if (a[i] <= a[j]) { tmp[k++] = a[i++]; // i++等于i:=i+1 } else { tmp[k++] = a[j++]; } } // 判断哪个子数组中有剩余的数据 int start = i; int end = q; if (j <= r) { start = j; end = r; } // 将剩余的数据拷贝到临时数组tmp while (start <= end) { tmp[k++] = a[start++]; } // 将tmp中的数组拷贝回a[p...r] for (i = 0; i <= r-p; ++i) { a[p+i] = tmp[i]; } } }-
稳定性:根据代码只有merge合并函数,我们将arr[p, q]跟arr[q+1,r]相同的数据取arr[p , q]即可保证稳定性,归并排序是一个稳定的排序算法
-
时间复杂度:
T(a) = T(b) + T(c) + K //k为将两个子问题a,b的结果合并成问题a消耗的时间 不仅递归求解的问题可以写成递推公式，递归代码的时间复杂度也可以写成递推公式 假设n个元素进行归并排序需要时间为T(n),则分解成两个子数组排序时间为T(n/2),而merge()函数合并两个游西子数组时间复杂度为O(n) 则 T(1) = C ; n = 1时,执行时间为常量级别的 T(n) = 2 *T(n/2) + n; n>1 分解公式为: T(n) = 2 * T(n/2) + n = 2 * (2 * T(n/4) + n/2) + n = 4 * T(n/4) + 2n = 4 * (2 * T(n/8) + n/4) + 2n = 8 * T(n/8) + 3n = 8 * (2 * T(n/16) + n/8) + 3n = 16 * T(n/16) + 4n ... = 2 ^k * T(n/2^k) + kn ... 所以:T(n) = 2^kT(n/2^k)+kn 当n/2^k = 1时 k = log2n 则T(n)=Cn+nlog2n 所以时间复杂度为O(nlogn) 归并排序的执行效率与要排序的原始数组的有序程度无关，其时间复杂度是非常稳定的都是相同的- 空间复杂度:合并的时候需要开辟内存控件为arr[n],所以需要的空间复杂度为O(n);
-
-
思想:
- 如果要排序数组中下标从p到r之间的一组数据,我们选择p到r之间的任意一个数据作为pivot作为分区点;
- 我们遍历p到r之间的数据,将小于pivot的放在左边,将大于pivot的放在右边,将pivot放在中间位置为q,则数组p到r将被分为三个部分,前面p->q-1之间都小于pivot,后面的q+1->r之间都大于pivot;
- 根据分治,递归思想,我们用递归排序下标从p -> q- 1之间的数据和 q+1->r之间的数据,直到区间缩小到1,就说明所有数据都有序了
-
递推公式为:
//递推公式 quick_sort(p...r) = quick_sort(p...q-1) + quick_sort(q+1...r) //终止条件为 p >= r -
伪代码为:
//快速排序,a是数组,n为数组大小 quick_sort(a , n){ quick_sort_c(a , 0 , n-1); } //快速排序递归函数, p, r为下标 quick_sort_c(a , p , r){ if(p >= r){ return ; } q = partition(a , p , r) //获取分区点 quick_sort_c(a , p , q - 1) quick_sort_c(a , q + 1 , r) }- partition分区函数就是随机选择一个元素作为pivot(一般选择p->r区间的最后一个元素,然后对a[p...r]分区,返回pivot的下标)
- partition分区函数一般使用原地排序算法实现,跟选择排序一样,他是不稳定的排序算法
-
真实代码:
public class QuickSortManage { // 快速排序，a是数组，n表示数组的大小 public static void quickSort(int[] a, int n) { quickSortInternally(a, 0, n-1); } // 快速排序递归函数，p,r为下标 private static void quickSortInternally(int[] a, int p, int r) { if (p >= r) return; int q = partition(a, p, r); // 获取分区点 quickSortInternally(a, p, q-1); quickSortInternally(a, q+1, r); } /** * * @param a 待排序数组 * @param p 数组的起始位置 * @param r 数组的终止位置 * @return 返回数组最后一位排序后所在数组位置的下标值 */ private static int partition(int[] a, int p, int r) { //获取p ,r的中位数取其中的中间值作为分区点 int q = (p + r) / 2 ; //得到三个值的中位数,然后给末尾交换 int inter = p < q ? (q < r ? q : p < r ? r : p) : (q > r ? q : p > r ? r : p); if (inter != r){ //交换q跟r a[inter] = a[inter] ^ a[r]; //一个数异或两次还是本身 x = x ^ y ^ y ; a[r] = a[inter] ^ a[r]; a[inter] = a[inter] ^ a[r]; } int pivot = a[r]; //将最后一位作为分区点 int i = p; for(int j = p; j < r; j++) { /** * 判断所有小于分区点的值跟其后第一个大于分区点的值交换位置 * 比如:数组 1,4,5,2,3 * 第一次遍历i = j = 0 ;交换第一个i,可以判断一下不交换位置了 * 第二次遍历 i = j = 1 ,此时 4 > 3 , i不变 j++ :i ->4 , j -> 5 * 第三次遍历 i = 1 , j = 2 , 此时 5 > 3 , i不变,j++ : i->4 , j -> 2 * 第四次遍历 i = 1 , j = 3 , 此时 2 < 3了,将i的值与j互换,即数组1,3位置元素互换后为 1,2,5,4,3 : i++ , j++ ; * 第五次遍历 i = 2 , j = 4 , 进入最后一位跳出for循环,则交换i跟r的值,排序为 1,2,3,4,5 * 此时返回的是i=2.即以3为分区点,再次循环分为1,2 跟 4,5划分 */ if (a[j] < pivot) { if (i != j){ //判断角标一致不在交换位置了,只是i++ ,j++ 操作 int tmp = a[i]; a[i] = a[j]; a[j] = tmp; } ++i; } } //将排序后的第一个大于povit的跟最后一个交换位置后,i之前的均小于povit,之后的均大于povit int tmp = a[i]; a[i] = a[r]; a[r] = tmp; System.out.println("i=" + i); return i; } } -
稳定性:由于获取分区点涉及到交换位置,所以是非稳定性的排序
-
原地排序算法:只使用了交换元素,空间复杂度为O(1)
-
时间复杂度:(大部分情况下为O(nlogn,极端情况下为O(n^2)可以优化避免))
- 如果每次都是中位数在最后一位:每次都分为大小相近的两个区间,公式同归并相同时间复杂度为O(nlogn)
- 最坏时间复杂度:如果数组已经有序,那么我们需要n次分区,而每次平均扫描n/2所以时间复杂度退化为O(n^2)
- 优化思路:
- pivot基准的获取思路:
- 固定位置,一般是首位后者末尾
- 随机选取基准,根据随机数得到角标,然后交换到末尾即可
- 三数取中:使用左端,右端和中心位置上的数比较去中位数交换到末尾即可
- 优化方式:
- 当待排序序列长度分割到一定大小后,使用插入排序比如末尾 - 起始 < 20的时候使用插入排序
- 将于pivot的元素聚在一起移到一起,下次划分过滤掉于pivot相同的数据
- pivot基准的获取思路:
-
递归于快排的区别
- 归并排序是由下到上,先处理子问题然后在合并;快排正好相反,由上到下,先分区在处理子问题
- 稳定性:归并排序稳定,快排不稳定
- 是否是原地算法:归并空间复杂度O(n),非原地算法,快排空间复杂度O(1)原地算法
- 时间复杂度:归并O(nlogn) , 快排大部分情况下O(nlogn),当完全有序为O(n^2)可以避免的;
- 算法核心:归并理解merge()合并函数,快排理解partition()分区函数;
