随笔-0  评论-0  文章-24  trackbacks-0
选择排序
      算法描述：首先找出A中的最小元素，并将其与A[0]中的元素交换。接着。找出A中的次最小元素，并将其与A[1]中的元素进行交换。对A中头n - 1个元素继续这一过程。
 1/*
 2    名称：选择排序
 3    时间复杂度：O(n * n)
 4*/
 5#include <iostream>
 6#include <time.h>
 7#include <stdlib.h>
 8using namespace std;
 9void selectSort(int*, int);
10int main(void)
11{
12    int n;
13    int *array;
14    srand(time(NULL));               /*void srand(unsigned seed)；*/
15    while (true)
16    {
17        cin >> n;
18        array = new int[n];
19        /*随机生成数组*/
20        for (int i = 0; i < n; ++i)
21        {
22            array[i] = rand() % 100; /*int rand(void)；*/
23        }
24
25        /*排序前*/
26        for (int i = 0; i < n; ++i)
27        {
28            cout << array[i] << ' ';
29        }
30        cout << endl;
31
32        /*选择排序*/
33        selectSort(array, n);
34
35        /*排序后*/
36        for (int i = 0; i < n; ++i)
37        {
38            cout << array[i] << ' ';
39        }
40        cout << endl;
41
42        delete array;
43    }
44    return 0;
45}
46void selectSort(int* array, int length)
47{
48    for (int i = 0; i < length; ++i)
49    {
50        int pivot = i;
51        /*从array[j .. length - 1]选择一个最小的与array[i]交换*/
52        for (int j = i + 1; j < length; ++j)
53        {
54            if (array[j] < array[pivot])
55            {
56                pivot = j;
57            }
58        }
59        /*如果最小的不是array[i],则交换*/
60        if (pivot != i)
61        {
62            int temp = array[i];
63            array[i] = array[pivot];
64            array[pivot] = temp;
65        }
66    }
67}
68


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

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


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