免费稳定网站空间,小网站搜什么关键词好,书城网站开发,网站建设推广优化岗位说明书一、排序算法的时间复杂度和空间复杂度 排序算法 平均时间复杂度 最坏时间复杂度 最好时间复杂度 空间复杂度 稳定性 冒泡排序 O(n) O(n) O(n) O(1) 稳定 直接选择排序 O(n) O(n) O(n) O(1) 不稳定 直接插入排序 O(n) O(n) O(n) O(1) 稳定 快速排序 O(n…
一、排序算法的时间复杂度和空间复杂度 排序算法 平均时间复杂度 最坏时间复杂度 最好时间复杂度 空间复杂度 稳定性 冒泡排序 O(n²) O(n²) O(n) O(1) 稳定 直接选择排序 O(n²) O(n²) O(n²) O(1) 不稳定 直接插入排序 O(n²) O(n²) O(n) O(1) 稳定 快速排序 O(nlogn) O(n²) O(nlogn) O(nlogn) 不稳定 堆排序 O(nlogn) O(nlogn) O(nlogn) O(1) 不稳定 归并排序 O(nlogn) O(nlogn) O(nlogn) O(n) 稳定 希尔排序 O(nlogn) O(n²)O(nlogn) O(1) 不稳定 计数排序 O(nk) O(nk) O(nk) O(nk) 稳定 基数排序 O(N*M) O(N*M) O(N*M) O(M) 稳定
注
1 归并排序可以通过手摇算法将空间复杂度降到O(1)但是时间复杂度会提高。
2 基数排序时间复杂度为O(N*M)其中N为数据个数M为数据位数。 1.1 复杂度辅助记忆
冒泡、选择、直接 排序需要两个for循环每次只关注一个元素平均时间复杂度为O(n²)一遍找元素O(n)一遍找位置O(n)快速、归并、希尔、堆基于二分思想log以2为底平均时间复杂度为O(nlogn)一遍找元素O(n)一遍找位置O(logn)
1.2 稳定性辅助记忆
稳定性记忆-“快希选堆”快牺牲稳定性 排序算法的稳定性排序前后相同元素的相对位置不变则称排序算法是稳定的否则排序算法是不稳定的。 二、理解时间复杂度
2.1 常数阶O(1)
int i 1;
int j 2;
i;
j;
int m i j; 2.2 对数阶O(logN)
int i 1;
while(in)
{i i * 2;
}2.3 线性阶O(n)
for(i0; in; i)
{System.out.println(hello);
}
2.4 线性对数阶O(n)
for(m1; mn; m)
{i 1;while(in){i i * 2;}
}
2.5 平方阶O(n) for(x1; in; x)
{for(i1; in; i){System.out.println(hello);}
}2.6 K次方阶O(n) for(i0; in; i){for(j0; in; i){for(k0; in; i){System.out.println(hello);}}}// k 3 , n ^ 3
上面从上至下依次的时间复杂度越来越大执行的效率越来越低。 三、空间复杂度
3.1 常数阶O(1) —— 原地排序
只用到 temp 这么一个辅助空间
原地排序算法就是空间复杂度为O(1)的算法不牵涉额外得到其他空间~ private static void swap(int[] nums, int i, int j) {int temp nums[i];nums[i] nums[j];nums[j] temp;}
2.2 对数阶O(logN) 2.3 线性阶O(n) int[] newArray new int[nums.length];for (int i 0; i nums.length; i) {newArray[i] nums[i];} 四、排序算法
4.1 冒泡排序
思路大的往后放 4.1.1 代码 private static void bubbleSort(int[] nums) {for (int i 0; i nums.length; i) {for (int j 0; j nums.length - 1 - i; j) {if (nums[j] nums[j 1]) {swap(nums, j, j 1);}}}}
4.1.2 复杂度
时间复杂度 N^2
空间复杂度1
最佳时间复杂度N^2 (因为就算你内部循环只对比不交换元素也是一样是N
稳定性稳定的 大于的才换小于等于的不交换 // { 0,1,2,3,4}private static void bubbleSort(int[] nums) {for (int i 0; i nums.length; i) {boolean isChange false;for (int j 0; j nums.length - 1 - i; j) {if (nums[j] nums[j 1]) {swap(nums, j, j 1);isChange true;}}if(!isChange){return;}}}
改进后的代码最佳时间复杂度 N 因为假如第一轮对比就没有任何元素交换那么可以直接退出也就是只有一次外循环 4.2 选择排序
思路最小的放最前 4.2.1 代码
private static void selectSort(int[] nums) {for (int i 0; i nums.length; i) {int minIndex i;for (int j i 1; j nums.length; j) {if (nums[j] nums[minIndex]) {minIndex j;}}swap(nums,minIndex,i);}}
4.2.2 复杂度
时间复杂度 N^2
空间复杂度1
最佳时间复杂度N^2
稳定性不稳定的 4.3 直接插入排序
思路往排序好的数组中找到合适的位置插进去 4.3.1 代码
private static void insertSort(int[] nums) {for (int i 1; i nums.length; i) {int temp nums[i];int j i - 1;for (; j 0 temp nums[j]; j--) {nums[j 1] nums[j];}nums[j 1] temp;}}
4.3.2 复杂度
时间复杂度 N^2
空间复杂度1
最佳时间复杂度N (因为你不进入内部循环。 [1,2,3,4,5] 稳定性稳定的 4.4 快速排序
思路利用数字target把数组切成两边左边比 target大后边比 target小 4.4.1 代码
/*** 快速排序算法* param nums 待排序的数组* param beginIndex 排序起始索引* param endIndex 排序结束索引*/
private static void quickSort(int[] nums, int beginIndex, int endIndex) {if (beginIndex endIndex) {return; // 递归终止条件当开始索引大于等于结束索引时表示已经完成排序}int mid getMid(nums, beginIndex, endIndex); // 获取中间索引用于分割数组quickSort(nums, beginIndex, mid - 1); // 对中间索引左侧的数组进行快速排序quickSort(nums, mid 1, endIndex); // 对中间索引右侧的数组进行快速排序
}/*** 获取分区中的中间元素的索引* param nums 待排序的数组* param beginIndex 分区的起始索引* param endIndex 分区的结束索引* return 中间元素的索引*/
private static int getMid(int[] nums, int beginIndex, int endIndex) {int target nums[beginIndex]; // 以数组的起始元素作为基准值int left beginIndex;int right endIndex;boolean right2left true; // 标识位表示当前从右往左搜索while (right left) {if (right2left) {while (right left nums[right] target) {right--;}if (right left) {nums[left] nums[right]; // 当右侧元素较大时将右侧元素移到插入位置right2left false; // 切换为从左往右搜索}} else {while (right left nums[left] target) {left;}if (right left) {nums[right] nums[left]; // 当左侧元素较小时将左侧元素移到插入位置right2left true; // 切换为从右往左搜索}}}nums[left] target; // 将基准值放入插入位置完成一轮交换return left;
}4.4.2 复杂度
时间复杂度 N Log N 每个元素找到中间位置的需要 LogN 时间N个元素就是NLogN
空间复杂度N Log N 递归调用需要栈空间 最差时间复杂度N ^ 2 比如正序数组 [1,2,3,4,5] 稳定性不稳定的 4.5 堆排序
思路最大放上面然后与最后元素交换继续建堆 4.5.1 代码
/*** 堆排序算法* param nums 待排序的数组* param beginIndex 排序的起始索引* param endIndex 排序的结束索引*/
private static void heapSort(int[] nums, int beginIndex, int endIndex) {if (beginIndex endIndex) {return; // 当开始索引大于等于结束索引时排序完成}for (int i endIndex; i beginIndex; i--) {createHeap(nums, i); // 构建最大堆swap(nums, 0, i); // 将最大元素移到数组末尾}
}/*** 构建最大堆* param nums 待构建的数组* param endIndex 当前堆的结束索引*/
private static void createHeap(int[] nums, int endIndex) {int lastFatherIndex (endIndex - 1) / 2;for (int i lastFatherIndex; i 0; i--) {int biggestIndex i;int leftChildIndex i * 2 1;int rightChildIndex i * 2 2;if (leftChildIndex endIndex) {biggestIndex nums[biggestIndex] nums[leftChildIndex] ? biggestIndex : leftChildIndex;}if (rightChildIndex endIndex) {biggestIndex nums[biggestIndex] nums[rightChildIndex] ? biggestIndex : rightChildIndex;}swap(nums, biggestIndex, i); // 调整堆确保最大元素位于堆顶}
}/*** 交换数组中两个元素的位置* param nums 数组* param i 索引1* param j 索引2*/
private static void swap(int[] nums, int i, int j) {int temp nums[i];nums[i] nums[j];nums[j] temp;
}4.5.2 复杂度
时间复杂度 N Log N 每个元素都要构建1次堆需要 LogN 时间N个元素就是NLogN任何情况下都一样
空间复杂度1 原地排序
最差时间复杂度N ^ 2 比如正序数组 [1,2,3,4,5]
稳定性不稳定的 4.6 归并排序
递归思路左右两边排序好了就已经排序好了 4.6.1 代码
// 归并排序的主方法
private static void mergeSort(int[] nums, int beginIndex, int endIndex) {// 如果起始索引大于等于结束索引表示只有一个元素或没有元素不需要排序if (beginIndex endIndex) {return;}// 计算数组的中间索引int mid beginIndex (endIndex - beginIndex) / 2;// 递归排序左半部分mergeSort(nums, beginIndex, mid);// 递归排序右半部分mergeSort(nums, mid 1, endIndex);// 合并左右两部分merge(nums, beginIndex, mid, endIndex);
}// 合并函数用于将左右两部分合并成一个有序的数组
private static void merge(int[] nums, int beginIndex, int mid, int endIndex) {int left beginIndex;int right mid 1;int[] newArrays new int[endIndex - beginIndex 1];int newArraysIndex 0;// 比较左右两部分的元素将较小的元素放入新数组while (left mid right endIndex) {newArrays[newArraysIndex] nums[left] nums[right] ? nums[left] : nums[right];}// 将剩余的左半部分元素复制到新数组while (left mid) {newArrays[newArraysIndex] nums[left];}// 将剩余的右半部分元素复制到新数组while (right endIndex) {newArrays[newArraysIndex] nums[right];}// 将合并后的新数组复制回原数组for (int i 0; i newArrays.length; i) {nums[beginIndex i] newArrays[i];}
}4.6.2 复杂度
时间复杂度 N Log N 每个元素都要递归需要 LogN 时间N个元素就是NLogN任何情况下都一样
空间复杂度N
稳定性稳定的 4.7 希尔排序
思路直接插入排序的升级版分段式插入排序 4.7.1 代码
private static void quickSort(int[] nums) {
// int gap nums.length / 2;
// while (gap 0) {for (int i 1; i nums.length; i) {int temp nums[i];int j;for (j i - 1; j 0 temp nums[j]; j--) {nums[j 1] nums[j];}nums[j 1] temp;}
// gap gap / 2;
// }}// 把上面的快速排序改成shell排序只需要把间隔1 改成gapprivate static void shellSort(int[] nums) {int gap nums.length / 2;while (gap 0) {for (int i gap; i nums.length; i) {int temp nums[i];int j;for (j i - gap; j 0 temp nums[j]; j j - gap) {nums[j gap] nums[j];// 如果当前元素比待插入元素大将当前元素向后移动}nums[j gap] temp; // 因为上边 jj-gap退出的时候j已经被剪掉1次了可能小于0了}gap gap / 2;}}
4.7.2 复杂度
时间复杂度 N Log N
空间复杂度1
稳定性稳定的
