已知关键字序列为{29,75,45,17,56,45,33}请分别用插入排序、选择排序、希尔排序、冒泡排序、快速排序对其进行排序,并写出排序过程。
插入排序概念:插入即表示将一个新的数据插入到一个有序数组中,并继续保持有序。例如有一个长度为N的无序数组,进行N-1次的插入即能完成排序;第一次,数组第1个数认为是有序的数组,将数组第二个元素插入仅有1个有序的数组中;第二次,数组前两个元素组成有序的数组,将数组第三个元素插入由两个元素构成的有序数组中......第N-1次,数组前N-1个元素组成有序的数组,将数组的第N个元素插入由N-1个元素构成的有序数组中,则完成了整个插入排序。
插入排序过程图:
插入排序代码:
public class InsertSort { public static void main(String[] args) { int[] arr = {29, 75, 45, 17, 56, 45, 33}; InsertSort is = new InsertSort(); is.sort(arr); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } } // 插入排序法 public void sort(int arr[]) { for (int i = 1; i < arr.length; i++) { int insertVal = arr[i]; // insertValue准备和前一个数比较 int index = i - 1; while (index >= 0 && insertVal < arr[index]) { // 将把arr[index]向后移动 arr[index + 1] = arr[index]; // 让index向前移动一位 index--; } // 将insertValue插入到适当位置 arr[index + 1] = insertVal; } } }