Insertion sort

Posted on | Edited on | Views: 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
//insertion sorting has 4 main different methods, including:
//1. direct insertion sorting
//2. binary insertion sorting
//3. 2way insertion sorting(cpp implementation)
//4. shell sorting

public class Insertion_sort{
	// ---------------------------------------------insetion sorting
	// direct insertion sorting
	static void insertion_sort(int[] nums) {
        for (int i = 1; i < nums.length; ++i) {
            int key = nums[i];
            int j = i - 1;
            /*
             * Move elements of nums[0..i-1], that are greater than key, to one position
             * ahead of their current position
             */
            while (j >= 0 && nums[j] > key) {
                nums[j + 1] = nums[j];
                j = j - 1; 
            }
            nums[j + 1] = key;
        }
	}
	/* // insertion sorting recursion version
	static void insertionSortRecursive(int[] input, int r) {
        if (r <= 0) return;
        insertionSortRecursive(input, r - 1);
        int key = input[r];
        int j = r - 1;
        while (j >= 0 && input[j] > key) {
            input[j + 1] = input[j];
            j = j - 1;
        }
        input[j + 1] = key;
    }*/

	// binary insertion sorting
	static void binary_insertion_sort(int[] nums) {
		for (int i = 1; i < nums.length; i++) {
			int temp = nums[i];
			int low = 0;
			int high = i - 1;
			while (low <= high) {
				int mid = (low + high) / 2;
				if (nums[mid] > temp)
					high = mid - 1;
				else
					low = mid + 1;
			}
			for (int j = i - 1; j >= high + 1; j--) {
				nums[j + 1] = nums[j];
			}
			nums[high + 1] = temp;
		}
	}

	// ---------------------------------------------shell sorting
	static void shellSort(int[] nums) {
		int gap = nums.length / 2;
		while (gap >= 1) {
			for (int i = gap; i < nums.length; i++) {// Start with the largest gap and work down to a gap of 1
				int tmp = nums[i];// save a[i] in temp and make a hole at position i
				int j = i - gap;// 前一个
				while (j >= 0 && nums[j] > tmp) {// Do a gapped insertion sort for this gap size.
					nums[j + gap] = nums[j];
					j = j - gap;
				}
				nums[j + gap] = tmp;
			}
			gap = gap / 2;
		}
	}

	//*********************************************
	//main function
	public static void main(String[] args) {
		int[][] new_array=new int[3][10];
		for(int i=0;i<3;i++){
			for (int j=0;j<10;j++) {
				new_array[i][j]=(int)(Math.random()*9+1);
			}
		}
		
		System.out.print("the original array is: ");
		for(int i:new_array[0])System.out.print(i);
		System.out.println();	
		System.out.print("after insertion sorting: ");	
		insertion_sort(new_array[0]);
		for(int i:new_array[0])System.out.print(i);
		System.out.println();
		System.out.println();
		
		System.out.print("the original array is: ");
		for(int i:new_array[1])System.out.print(i);
		System.out.println();
		System.out.print("after binary insertion sorting: ");	
		binary_insertion_sort(new_array[1]);
		for(int i:new_array[1])System.out.print(i);
		System.out.println();
		System.out.println();
		
		System.out.print("the original array is: ");
		for(int i:new_array[2])System.out.print(i);
		System.out.println();	
		System.out.print("after Shell sorting: ");	
		shellSort(new_array[2]);
		for(int i:new_array[2])System.out.print(i);
		
	}
}

Appendix: 2way_insertion_sorting

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<stdio.h>
#include<stdlib.h>

int main()
{
	int n = 8;
	int num[8] = { 49,38,65,97,76,13,27,49 };        // 待排序数组
	int temp[8] = { 0 };                             // 辅助数组
	int final_num = 0;                               // 尾指针（非真实指针，只代表数组下标）
	int first_num = 0;                               // 头指针（同上，且开始均指向0）

	temp[0] = num[0];                                // 先确定第一个位置，并以此为判断依据
	for (int i = 1; i < n; ++i)                      // 从第二个数开始插入排序
	{
		if (temp[final_num] < num[i])                // 如果待插数字比尾部数字还大，则插在尾部 
													 // 数字后面，并把尾部指针向后移动一位
		{
			final_num = (final_num + 1 + n) % n;
			temp[final_num] = num[i];
		}
		else if (temp[first_num] > num[i])           // 如果待插数字比头部数字还小，则插在头部
													 // 数字后面，并把头部指针向前移动一位
		{
			first_num = (first_num - 1 + n) % n;
			temp[first_num] = num[i];
		}
		else if (temp[0] <= num[i])                  // 如果比头部数字大，比尾部数字小
													 // 则比较该数字是否比辅助数组的第一个数大
													 // 如果大的话，从final_num往前找，找到
													 // 位置后插进去，否则与上述步骤相反
		{
			int k = (final_num + 1 + n) % n;
			while (temp[((k - 1) + n) % n] > num[i])
			{
				temp[(k + n) % n] = temp[(k - 1 + n) % n];
				k = (k - 1 + n) % n;
			}
			temp[(k + n) % n] = num[i];
			final_num = (final_num + 1 + n) % n;
		}
		else
		{
			int k = (first_num - 1 + n) % n;
			while (temp[((k + 1) + n) % n] < num[i])
			{
				temp[(k + n) % n] = temp[(k + 1 + n) % n];
				k = (k + 1 + n) % n;
			}
			temp[(k + n) % n] = num[i];
			first_num = (first_num - 1 + n) % n;
		}
		
		for (int i = 0; i < n; ++i)                  // 每次排序都输出辅助数组序列
		{
			printf("%d\t", temp[i]);
		}
		printf("\n");
		printf("first=%d final=%d\n", first_num, final_num);
	}
	for (int i = 0; i < n; ++i)                      // 根据辅助数组确定新序列
	{
		num[i] = temp[(first_num + i) % n];
		printf("%d\t", num[i]);
	}
	return 0;
}

0%