实例040 使用直接插入法对数组排序

发表于 分类于 ， Waline： 本文字数： 5.5k 阅读时长 ≈ 5 分钟

实例040 使用直接插入法对数组排序

实例说明

本实例演示如何使用直接插入排序法对一维数组进行排序。运行本实例,首先单击“随机生成数组”按钮,生成一个随机数组,并显示在左边的文本框中;然后单击“排序”按钮,使用直接插入排序法对生成的一维数组进行排序,并将排序后的一维数组显示在右边的文本框中。实例的运行效果如图513所示。

实现过程

(3)编写“随机生成数组”按钮的事件处理方法,在该方法中利用Ra象的法生成随机为数组设置初始值。关键代码如:

(4)编写“排序”按钮的事件处理方法,在该方法中使用直接插入排序算法对数组进行排序,并将排序后的数组显示到界面中。关键代码如下

技术要点

本实例主要用到了直接插入排序算接插入排序算法的实现原理进行详细讲解排序是将录插序使得到的新数列仍然有序。插算法的思想是:
将n个有序数存放在数组a中,要插入的数为x,首先确定x插在数组中的位置p,数组中p之后的元素都向后移一个位置,空出a(p),将x放入a(p)。这样即可实现插入后数列仍然有序。
使用插入排序法排序的过程如图514所示。

完整代码

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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
package com.lan;

import java.awt.EventQueue;
import java.awt.Font;
import java.awt.GridBagConstraints;
import java.awt.GridBagLayout;
import java.awt.Insets;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.util.Random;
import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.JScrollPane;
import javax.swing.JTextArea;
import javax.swing.border.EmptyBorder;

public class InsertSort extends JFrame
{
    private static final long serialVersionUID = -8006819934162242254L;
    private JPanel contentPane;
    // 待排序的数组
    private int[] array = new int[10];
    /**
     * Launch the application.
     */
    public static void main(String[] args)
    {
        EventQueue.invokeLater(new Runnable() {
            public void run()
            {
                try
                {
                    InsertSort frame = new InsertSort();
                    frame.setVisible(true);
                } catch (Exception e)
                {
                    e.printStackTrace();
                }
            }
        });
    }

    /**
     * Create the frame.
     */
    public InsertSort() {
        setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        setBounds(100, 100, 450, 300);
        contentPane = new JPanel();
        contentPane.setBorder(new EmptyBorder(5, 5, 5, 5));
        setContentPane(contentPane);
        GridBagLayout gbl_contentPane = new GridBagLayout();
        gbl_contentPane.columnWidths = new int[]{0, 0};
        gbl_contentPane.rowHeights = new int[]{0, 0, 0, 0, 0};
        gbl_contentPane.columnWeights = new double[]{1.0, Double.MIN_VALUE};
        gbl_contentPane.rowWeights = new double[]{0.0, 0.0, 1.0, 0.0, Double.MIN_VALUE};
        contentPane.setLayout(gbl_contentPane);

        JTextArea textAreaArray = new JTextArea();
        // textArea.setRows(1);
        GridBagConstraints gbc_textAreaArray = new GridBagConstraints();
        gbc_textAreaArray.insets = new Insets(0, 0, 5, 0);
        gbc_textAreaArray.fill = GridBagConstraints.BOTH;
        gbc_textAreaArray.gridx = 0;
        gbc_textAreaArray.gridy = 0;
        contentPane.add(textAreaArray, gbc_textAreaArray);

        JButton buttonCreateRandomArray = new JButton("生成随机数组");
        buttonCreateRandomArray.addActionListener(new ActionListener() {

            public void actionPerformed(ActionEvent e)
            {
                textAreaArray.setText("");
                Random random = new Random();
                for (int i = 0; i < array.length; i++)
                {
                    array[i] = random.nextInt(50);
                    textAreaArray.append(String.valueOf(array[i]));
                    if (i < array.length - 1)
                    {
                        textAreaArray.append(",");
                    }
                }
            }
        });
        GridBagConstraints gbc_buttonCreateRandomArray = new GridBagConstraints();
        gbc_buttonCreateRandomArray.insets = new Insets(0, 0, 5, 0);
        gbc_buttonCreateRandomArray.gridx = 0;
        gbc_buttonCreateRandomArray.gridy = 1;
        contentPane.add(buttonCreateRandomArray, gbc_buttonCreateRandomArray);

        JScrollPane scrollPane = new JScrollPane();
        GridBagConstraints gbc_scrollPane = new GridBagConstraints();
        gbc_scrollPane.fill = GridBagConstraints.BOTH;
        gbc_scrollPane.insets = new Insets(0, 0, 5, 0);
        gbc_scrollPane.gridx = 0;
        gbc_scrollPane.gridy = 2;
        contentPane.add(scrollPane, gbc_scrollPane);

        JTextArea textAreaShow = new JTextArea();
        textAreaShow.setFont(new Font("Monospaced", Font.BOLD, 14));
        scrollPane.setViewportView(textAreaShow);

        JButton buttonInsertSort = new JButton("直接插入排序");
        buttonInsertSort.addActionListener(new ActionListener() {
            public void actionPerformed(ActionEvent e)
            {
                textAreaShow.setText("");
                insertSort(textAreaShow);
            }

            private void insertSort(JTextArea textAreaShow)
            {
                int toInsert;
                for (int i = 1; i < array.length; i++)
                {
                    // 缓存要插入的元素
                    toInsert = array[i];
                    // 遍历前面已经排序要的序列
                    int j = i - 1;
                    // 如果前面的一个元素比要插入的元素大,就将这个大的元素后移一格
                    while (j >= 0 && array[j] > toInsert)
                    {
                        // 将比要插入的元素大的元素全部向后移动一格
                        array[j + 1] = array[j];
                        // 比较下一个格
                        j--;
                    }
                    //
                    array[j + 1] = toInsert;
                    // printArray(textAreaShow);
                    printStep(textAreaShow, i);
                }
            }

            private void printStep(JTextArea textAreaShow, int i)
            {
                textAreaShow.append("[");
                for (int k = 0; k < array.length; k++)
                {
                    textAreaShow.append(String.valueOf(array[k]));
                    if (k == i)
                    {
                        textAreaShow.append("]");
                    }
                    if (k < array.length - 1)
                    {
                        textAreaShow.append(",");
                    }
                }
                textAreaShow.append("\n");
            }
        });
        GridBagConstraints gbc_buttonInsertSort = new GridBagConstraints();
        gbc_buttonInsertSort.gridx = 0;
        gbc_buttonInsertSort.gridy = 3;
        contentPane.add(buttonInsertSort, gbc_buttonInsertSort);
    }
}

运行效果

待排序数组:

1
41,22,37,46,45,0,42,12,10,34

排序效果:

1
2
3
4
5
6
7
8
9
[22,41],37,46,45,0,42,12,10,34
[22,37,41],46,45,0,42,12,10,34
[22,37,41,46],45,0,42,12,10,34
[22,37,41,45,46],0,42,12,10,34
[0,22,37,41,45,46],42,12,10,34
[0,22,37,41,42,45,46],12,10,34
[0,12,22,37,41,42,45,46],10,34
[0,10,12,22,37,41,42,45,46],34
[0,10,12,22,34,37,41,42,45,46]

待排序数组

1
11,34,35,15,36,0,13,24,16,16

排序效果:

1
2
3
4
5
6
7
8
9
[11,34],35,15,36,0,13,24,16,16
[11,34,35],15,36,0,13,24,16,16
[11,15,34,35],36,0,13,24,16,16
[11,15,34,35,36],0,13,24,16,16
[0,11,15,34,35,36],13,24,16,16
[0,11,13,15,34,35,36],24,16,16
[0,11,13,15,24,34,35,36],16,16
[0,11,13,15,16,24,34,35,36],16
[0,11,13,15,16,16,24,34,35,36]