插入排序insertionSort

本文主要是介绍插入排序insertionSort，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

插入排序就是每一步都将一个待排数据按其大小插入到已经排序的数据中的适当位置，直到全部插入完毕。

具体算法描述如下：

⒈ 从第一个元素开始，该元素可以认为已经被排序

⒉ 取出下一个元素，在已经排序的元素序列中从后向前扫描

⒊ 如果该元素（已排序）大于新元素，将该元素移到下一位置

⒋ 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置

算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。

Java版本

/**
*插入排序
*/

 public static void insertionSort(int[] a) {int N = a.length;// put smallest element in position to serve as sentinelint exchanges = 0;for (int i = N-1; i > 0; i--) {if (a[i] < a[i-1]) {int swap=a[i-1];a[i-1] = a[i];a[i] = swap;exchanges++;}}if (exchanges == 0) return;// insertion sort with half-exchangesfor (int i = 2; i < N; i++) {int v = a[i];int j = i;while (v < a[j-1]) {a[j] = a[j-1];j--;}a[j] = v;}}

这篇关于插入排序insertionSort的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---