随笔-0  评论-0  文章-24  trackbacks-0
插入排序(递归)
      插入排序可以如下改写成一个递归过程：为排序A[0 .. n - 1],先递归地排序A[0 .. n - 2],然后再将A[n - 1]插入到已排序的数组A[0 .. n - 2]中去。
 1/*
 2    名称：插入排序
 3    最坏时间复杂度（降序）：O(n * n)
 4    最好时间复杂度（升序）：O(n)
 5*/
 6#include <iostream>
 7#include <time.h>
 8#include <stdlib.h>
 9using namespace std;
10void insertSortRecursion(int*, int);
11int main(void)
12{
13    int n;
14    int *array;
15    srand(time(NULL));               /*void srand(unsigned seed)；*/
16    while (true)
17    {
18        cin >> n;
19        array = new int[n];
20        /*随机生成数组*/
21        for (int i = 0; i < n; ++i)
22        {
23            array[i] = rand() % 100; /*int rand(void)；*/
24        }
25
26        /*排序前*/
27        for (int i = 0; i < n; ++i)
28        {
29            cout << array[i] << ' ';
30        }
31        cout << endl;
32
33        /*插入排序*/
34        insertSortRecursion(array, n);
35
36        /*排序后*/
37        for (int i = 0; i < n; ++i)
38        {
39            cout << array[i] << ' ';
40        }
41        cout << endl;
42
43        delete array;
44    }
45    return 0;
46}
47void insertSortRecursion(int* array, int length)
48{
49    /*只有一个元素直接return*/
50    if (length == 1)
51    {
52        return ;
53    }
54    insertSortRecursion(array, length - 1);
55    if (array[length - 1] < array[length - 2])
56    {
57        int temp = array[length - 1];
58        int i;
59        /*寻找插入位置*/
60        for (i = length - 2; i >= 0 && array[i] > temp; --i)
61        {
62            array[i + 1] = array[i];
63        }
64        array[i + 1] = temp;
65    }
66}
67

posted on 2012-10-22 21:26 zhuxin 阅读(542) 评论(0)  编辑 收藏 引用 所属分类: 排序算法

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


Powered by: 博客园 模板提供：沪江博客 Copyright ©2024 zhuxin