插入排序


插入排序简介:

插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序,时间复杂度为O(n^2)。是稳定的排序方法。

具体算法描述如下:

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

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

⒊ 如果该元素(已排序)大于新元素,将该元素移到下一位置

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

⒌ 将新元素插入到下一位置中

⒍ 重复步骤2~5

代码实现(java):

	// 默认升序
	public void InsertSort(int[] arr) {
		
		int arrLen = arr.length;
		
		for (int i = 1; i < arrLen; i++) {

			int tmp = arr[i];
			int k = i - 1;
			for (; k >= 0 && tmp < arr[k]; k--) {

				arr[k + 1] = arr[k];
			}
			arr[k + 1] = tmp;
		}
	}



联系我们 | 友情链接