简化的插入排序
时间: 2023-07-02 19:23:02 浏览: 57
好的,插入排序的基本思想是将一个待排序的元素插入到已排序序列中的适当位置,使得插入后依然有序。简化的插入排序的实现如下:
1. 从第二个元素开始,依次将每个元素插入到已排序序列中。
2. 对于每个待插入的元素,从它前一个元素开始向前遍历已排序序列,找到它应该插入的位置。
3. 将待插入元素插入到该位置。
实现代码如下:
```
void insertion_sort(int arr[], int n)
{
int i, j, tmp;
for (i = 1; i < n; i++) {
tmp = arr[i];
for (j = i - 1; j >= 0 && arr[j] > tmp; j--) {
arr[j + 1] = arr[j];
}
arr[j + 1] = tmp;
}
}
```
这样就完成了简化的插入排序,时间复杂度为 $O(n^2)$。
相关问题
pta简化的插入排序
对于本题,我们可以使用插入排序来实现。插入排序的基本思想是将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录数增加1的有序表。具体实现过程如下:
1. 从第一个元素开始,该元素可以认为已经被排序;
2. 取出下一个元素,在已经排序的元素序列中从后向前扫描;
3. 如果该元素(已排序)大于新元素,将该元素移到下一位置;
4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
5. 将新元素插入到该位置后;
6. 重复步骤2~5。
下面是使用Python实现的简化版插入排序代码:
```python
n = int(input()) # 输入单词个数
words = []
for i in range(n):
words.append(input()) # 输入单词
for i in range(1, n):
temp = words[i]
j = i - 1
while j >= 0 and len(words[j]) > len(temp):
words[j+1] = words[j]
j -= 1
words[j+1] = temp
for word in words:
print(word) # 输出排序后的单词
```
java简化的插入排序
Java中的简化插入排序是一种基于比较的排序算法,它通过将待排序的元素逐个插入已排序序列中的适当位置来完成排序。以下是简化插入排序的实现步骤:
1. 遍历待排序序列,从第二个元素开始(假设第一个元素已经是有序的)。
2. 将当前元素与已排序序列进行比较,找到合适的位置插入。
3. 将当前元素插入到合适的位置后,将已排序序列中的元素依次后移。
4. 重复步骤2和3,直到遍历完所有待排序元素。
下面是Java代码示例:
```java
public class InsertionSort {
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
public static void main(String[] args) {
int[] arr = {5, 2, 8, 3, 1};
insertionSort(arr);
for (int num : arr) {
System.out.print(num + " ");
}
}
}
```
输出结果为:1 2 3 5 8
阅读全文