插入、冒泡、归并、快排时间复杂度和空间复杂度

1. 插入排序

/*** 插入排序的* 1.时间复杂度为O(n^2)* 2. O(1)的额外空间的排序* 3. 平均情况为O(n*n)** @param array* @return*/public static int[] insertSort(int[] array) {for (int index = 0; index < array.length; index++) {int temp = array[index];  //将index位的数据拿出来，放到临时变量里，这时index位置就空出来了.int leftIndex = index - 1;while (leftIndex >= 0 && array[leftIndex] > temp) {  //开始将左面的数据与当前index位的数据（即temp）进行比较array[leftIndex + 1] = array[leftIndex];leftIndex--;}array[leftIndex + 1] = temp;}return array;}

2.冒泡排序

/*** 冒泡排序* 最优的时间复杂度为：O( n^2 )* 最差的时间复杂度为：O( n^2 )；* 平均的时间复杂度为：O( n^2 )；* 平均的空间复杂度为：O(1)；** @param array*/public static void sort(int[] array) {for (int i = 0; i < array.length - 1; i++) {for (int j = 0; j < array.length - 1 - i; j++) {if (array[j] > array[j + 1]) {int temp = array[j];array[j] = array[j + 1];array[j + 1] = temp;}}}}

3.归并排序

/*** 归并排序 归并排序是一种稳定的排序。* 可用顺序存储结构。也易于在链表上实现。o* 对长度为n的文件，需进行趟二路归并，每趟归并的时间为O(n)，故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlgn)。* 需要一个辅助向量来暂存两有序子文件归并的结果，故其辅助空间复杂度为O(n)，显然它不是就地排序。** @param array* @param low* @param mid* @param high*/public static void mergeArray(int[] array, int low, int mid, int high) {int[] temp = new int[array.length];int i = low;  //i右数组第一个元素索引int j = mid + 1;  //j左数组的第一个元素索引int k = 0;// k 记录临时数组的索引// 从两个数组中取出最小的放入临时数组while (i <= mid && j <= high) {if (array[i] > array[j]) temp[k++] = array[j++];else temp[k++] = array[i++];}// 剩余部分依次放入临时数组（实际上两个while只会执行其中一个）while (i <= mid) temp[k++] = array[i++];while (j <= high) temp[k++] = array[j++];// 将临时数组中的内容拷贝回原数组中for (int x = 0; x < k; x++) array[x + low] = temp[x];}public static void mergeSort(int[] array, int low, int high) {if (low < high) {int mid = (low + high) / 2;            // 找出中间索引mergeSort(array, low, mid);            // 对左边数组进行递归mergeSort(array, mid + 1, high);  // 对右边数组进行递归mergeArray(array, low, mid, high);     // 合并}}

4. 快速排序

/*** 快排* 快排在最糟糕得情况下时间复杂度是O(n²)，平均的复杂度是O(nlogn)* 主要是递归造成的栈空间的使用，最好情况，递归树的深度为log2n，* 其空间复杂度也就为O(logn)，最坏情况，需要进行n‐1递归调用，其空间复杂度为O(n)，平均情况，空间复杂度也为O(logn)。* @param array* @param low* @param high* @return*/public static int getIndex(int[] array, int low, int high) {int temp = array[low]; //记录一个标值的值while (low < high) {while (low < high && array[high] > temp) high--; //1. 队尾元素大于基准元素的时候 high--array[low] = array[high];                      // 如果队尾元素小于tmp了,需要将其赋值给lowwhile (low < high && array[low] < temp) low++;  //2. 队首元素小于基准元素的时候 low++array[high] = array[low];                        // 当队首元素大于tmp时,需要将其赋值给high}array[low] = temp;return low;}public static void quickSort(int[] array, int low, int high) {if (low < high) {int index = getIndex(array, low, high);quickSort(array, low, index - 1);quickSort(array, index + 1, high);}}

5.测试数据

public static void main(String[] args) {int[] array = {38, 65, 97, 76, 13, 27, 49};insertSort(array);System.out.print("插入排序从小到大排序后的结果是:");for (Integer i : array) {System.out.print(i + " ");}System.out.println();int[] array1 = {38, 65, 97, 76, 13, 27, 49};sort(array1);System.out.print("冒泡排序从小到大排序后的结果是:");for (Integer i : array1) {System.out.print(i + " ");}System.out.println();int[] array2 = {38, 65, 97, 76, 13, 27, 49};mergeSort(array2, 0, array2.length - 1);System.out.print("归并排序从小到大排序后的结果是:");for (Integer i : array2) {System.out.print(i + " ");}System.out.println();int[] array3 = {38, 65, 97, 76, 13, 27, 49};quickSort(array3, 0, array3.length - 1);System.out.print("快速排序从小到大排序后的结果是:");for (Integer i : array3) {System.out.print(i + " ");}}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！