排序的相关概念

        排序：所谓排序，就是使一串记录，按照其中的某个或某几个关键字的大小，递增或递减排列起来的操作。

        稳定性：在待排序的记录序列中，存在多个具有相同关键字的记录，若经过排序，这些记录的相对次序保持不变，则称这种排序算法是稳定的。

        内部排序：把数据全部加载到内存中进行排序。

        外部排序：数据太多，内存不能存储了，将数据放到磁盘、U盘上进行排序。

排序算法的分类

插入排序：直接插入排序、希尔排序

选择排序：选择排序、堆排序

交换排序：冒泡排序、快速排序

归并排序：归并排序

排序算法的实现

1.插入排序

1.1直接插入排序

基本思想：将待排序的记录，按照关键字的大小，逐个插入到一个有序序列中，直到所有记录插完为止。

代码实现:

import java.util.Arrays;
//插入排序
public class Sort1 {public static void main(String[] args) {int[] arr = {2, 3, 1, 6, 5};Sort1(arr);System.out.println(Arrays.toString(arr));}public static void Sort1(int[] arr) {for (int i = 1; i < arr.length; i++) {int tmp = arr[i];int j = i-1;for (; j >=0 ; j--) {if (arr[j]>tmp){arr[j+1]=arr[j];}else {break;}}arr[j+1]=tmp;}}
}

特性总结：

1.元素集合越接近有序，只需要少量的插入操作，就可以完成整个排序工作，此时直接插入排序算法的时间效率越高。

2.时间复杂度：O(n^2)       最好情况：O(n)

3.空间复杂度：O(1)

4.稳定性：稳定

1.2希尔排序（缩小增量法）

基本思想：希尔排序，通过增量(gap)将元素两两分组，对每组使用直接插入排序算法排序；增量(gap)逐渐减少，当增量(gap)减至1时，整个数据恰被分成一组，最后进行一次插入排序，整个数组就有序了。

代码实现：

//希尔排序public static void shellSort(int[] arr) {int gap = arr.length;while (gap > 1) {shell(arr,gap);gap=gap/2;}shell(arr,1);}public static void shell(int[] arr,int gap){for (int i = gap; i =0 ; j -= gap) {if (arr[j]>tmp){arr[j+gap]=arr[j];}else {break;}}arr[j+gap]=tmp;}}

特性总结：  

1.希尔排序是对直接插入排序的优化。(当gap>1时都是预排序，目的是让数组更接近于有序。当gap=1时，数组已接近有序，此时的最后一次直接插入排序效率最高。整体可以达到优化的结果。)

2.平均时间复杂度：O(n^1.5)       最好情况：O(n^1.3)

3.空间复杂度：O(1)

4.稳定性：稳定

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