数据结构排序算法总结

news/2024/7/27 7:33:02/文章来源:https://blog.csdn.net/weixin_44340277/article/details/135530561

直接插入排序 + 折半插入排序 + 希尔排序

冒泡排序 + 快速排序

选择排序 + 堆排序

归并排序

1.直接插入排序

前面的有序后面的无序，无序元素插入到前面的有序列表中

        int len = nums.length, i = 1, j = 0;for(i=1; i<len; i++){int ele = nums[i];// 插入过程for(j = i-1; j >= 0 && nums[j] > ele; j--)nums[j+1] = nums[j];nums[j+1] = ele;}return nums;

最坏时间复杂度 $O(n^2)$ ，最好时间复杂度 $O(n)$ ，空间复杂度 $O(1)$ ，稳定排序

2.折半插入排序：

折半插入排序可以拆分为 折半查找插入位置 + 数组插入

具体折半查找过程内部的细节总结折半查找过程-CSDN博客

        int i, j, ele, m, low, high, len = nums.length;for (i = 1; i < len; i++){ele = nums[i];// 折半查找low = 0; high = i-1;while (low <= high){m = (low +high) / 2;if(nums[m] > ele)high = m-1;elselow = m+1;}// 排序for (j = i-1; j>=low; j--)nums[j+1] = nums[j];nums[j+1] = ele;}return nums;

最坏时间复杂度 $O(n^2)$ ，最好时间复杂度 $O(n\log n)$ ，空间复杂度 $O(1)$ ，稳定排序.

3.冒泡排序：

        // 外层循环控制趟数for (int i = 0; i < n - 1; i++) {flag =false;// 内层循环进行比较和交换for (int j = 0; j < n - i - 1; j++) {if (arr[j] > arr[j + 1]) {swap(arr[j], arr[j+1]);flag = true;}}}

最坏时间复杂度 $O(n^2)$ ，最好时间复杂度 $O(n)$ ，空间复杂度 $O(1)$ ，稳定排序.

4.快速排序：

    public int partition(int[] nums, int left, int right){int pivot = nums[left];while(left < right){while(left < right && pivot <= nums[right]) right--;nums[left] = nums[right];while(left < right && pivot >= nums[left])left++;nums[right] = nums[left];}nums[left] = pivot;return left;}

    public void quickSort(int[] nums, int left, int right){if(left < right){int partition = partition(nums, left, right);quickSort(nums, left, partition-1);quickSort(nums, partition+1, right);}}

最坏时间复杂度 $O(n^2)$ ，最好时间复杂度 $O(n\log n)$ ，空间复杂度 $O(n\log n)$ ，不稳定排序.

每一次确定一个点的最终位置，然后把整个数组划分两部分。形成递归树，最坏情况是树高=n，且每一层都要遍历一次数组。空间复杂度就是整个递归树。

可参考快速排序最好，最坏，平均复杂度分析_对n个记录进行快速排序,在最坏的情况下,其时间复杂度是-CSDN博客

5.选择排序

    public void selectSort(int[] nums){for(int i=0; i<nums.length; i++){int index = i;int min = nums[i];for(int j=i; j<nums.length; j++){index = nums[j] < min ? j:index;min = nums[j] < min ? nums[j] : min;}nums[index] = nums[i];nums[i] = min;}}

最坏时间复杂度 $O(n^2)$ ，最好时间复杂度 $O(n^2)$ ，空间复杂度 $O(1)$ ，不稳定排序

6.堆排序

分为建堆，调整，排序。

建堆build_heap: len/2的位置往前遍历 adjust每一个节点。

    public void buildHeap(int[] nums, int len){for(int i=(len)/2; i>0; i--){adjust(nums, i, len);}}

调整adjust： for遍历子节点，顶点往下传。

    public void adjust(int[] nums, int k, int len){int val = nums[k];for(int i=2*k; i<=len; i=i*2){if(i+1 <= len && nums[i+1] > nums[i])i = i+1;if(nums[i] > val){nums[k] = nums[i];k = i;}elsebreak;}nums[k] = val;}

整合堆排序 heap_sort

    public void heapSort(int[] nums, int len){buildHeap(nums, len);for(int i=len; i>1; i--){swap(nums,1,i);adjust(nums,1,i-1);}}

最坏时间复杂度 $O(n\log n)$ ，最好时间复杂度 $O(n\log n)$ ，空间复杂度 $O(1)$ ，不稳定排序.

7.归并排序

把两个有序的子数组合并为一个大的有序数组。

merge 合并函数

    public void merge(int[] nums, int left, int mid, int right){int[] arr = new int[right-left+1];for(int i=0; i<arr.length; i++){arr[i] = nums[left+i];}int i = 0;int j = mid-left+1;int k = left;while(i <= mid-left && j <= right-left && k <= right){if(arr[i] <= arr[j])nums[k++] = arr[i++];elsenums[k++] = arr[j++];}while(i <= mid-left) nums[k++] = arr[i++];while(j <= right-left)nums[k++] = arr[j++];}

递归拆分数组

    public void mergeSort(int[] nums, int left, int right){if(left < right){int mid = (left + right) / 2;mergeSort(nums, left, mid);mergeSort(nums, mid+1, right);merge(nums,left, mid, right);}}

最坏时间复杂度 $O(n\log n)$ ，最好时间复杂度 $O(n\log n)$ ，空间复杂度 $O(n)$ ，稳定排序.

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.luyixian.cn/news_show_925429.aspx

如若内容造成侵权/违法违规/事实不符，请联系dt猫网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！