[转帖]  Linux下C实现选择排序_Android, Python及开发编程讨论区_Weblogic技术|Tuxedo技术|中间件技术|Oracle论坛|JAVA论坛|Linux/Unix技术|hadoop论坛_联动北方技术论坛  
网站首页 | 关于我们 | 服务中心 | 经验交流 | 公司荣誉 | 成功案例 | 合作伙伴 | 联系我们 |
联动北方-国内领先的云技术服务提供商
»  游客             当前位置:  论坛首页 »  自由讨论区 »  Android, Python及开发编程讨论区 »
总帖数
1
每页帖数
101/1页1
返回列表
0
发起投票  发起投票 发新帖子
查看: 3673 | 回复: 0   主题: [转帖]  Linux下C实现选择排序        下一篇 
luxiaofan
注册用户
等级:上尉
经验:705
发帖:67
精华:0
注册:2012-10-8
状态:离线
发送短消息息给luxiaofan 加好友    发送短消息息给luxiaofan 发消息
发表于: IP:您无权察看 2012-10-12 15:32:58 | [全部帖] [楼主帖] 楼主

选择排序,将待排序序列分为两个序列:已排序序列和未排序序列。每次从未排序序列中,选择一个最小的元素,存放在到已排序序列的最后,直到所有元素排序完毕。关键代码如下:

1、选择排序头文件:selectSort.h

#ifndef SELECTSORT_H
#define SELECTSORT_H
extern void selectSort(int *pArr, const int length);
#endif


2、选择排序源文件:selectSort.c

#include "selectSort.h"
void selectSort(int *pArr, const int length)
{
      int i,j,min,tmp;
      for(i=0; i<length-1; i++)
      {
            min =i;
            for(j=i+1; j<length; j++)
            {
                  if(*(pArr+min)>*(pArr+j))
                  {
                        min=j;
                  }
            }
            if(min!=i)
            {
                  tmp=*(pArr+i);
                  *(pArr+i)=*(pArr+min);
                  *(pArr+min)=tmp;
            }
      }
}


3、main头文件:main.h

#ifndef MAIN_H
#define MAIN_H
#include<stdio.h>
#include "selectSort.h"
int main(void);
void showArr(const int *pArr, const int length);
void initRandomArr(int *pArr, const int length);
#endif


4、main源文件:main.c

#include "main.h"
int main(void)
{
      printf("Input array length:\n");
      int length;
      scanf("%d", &length);
      if(length<0)
      {
            printf("Array length must be larger 0\n");
            return 1;
      }
      int arr[length];
      initRandomArr(arr, length);
      printf("Get random array :\n");
      showArr(arr, length);
      selectSort(arr, length);
      printf("select sort result:\n");
      showArr(arr, length);
      return 0;
}
void showArr(const int *pArr, const int length)
{
      int i;
      for(i=0; i<length; i++)
      {
            printf("%d ", *(pArr+i));
      }
      printf("\n");
}
void initRandomArr(int *pArr, const int length)
{
      int i;
      srand(time(NULL));
      for(i=0; i< length; i++)
      {
            *(pArr+i)=rand()%1000;
      }
}


5、编译程序:

[root@localhost selectSort]$ gcc -c main.c
[root@localhost selectSort]$ gcc -c selectSort.c
[root@localhost selectSort]$ gcc -o main main.o selectSort.o


执行可执行文件main,大致如下:

[root@localhost selectSort]$ ./main
Input array length:
8
Get random array :
906 968 161 208 757 885 370 691
select sort result:
161 208 370 691 757 885 906 968


选择排序时间复杂度О(n²), 交换次数O(n),已经有序的最好情况下,交换0次;逆序的最坏情况下,交换n-1次。交换次数比冒泡排序少多了,由于交换所需CPU时间比比较所需的CPU时间多,n值较小时,选择排序比冒泡排序快。




赞(0)    操作        顶端 
总帖数
1
每页帖数
101/1页1
返回列表
发新帖子
请输入验证码: 点击刷新验证码
您需要登录后才可以回帖 登录 | 注册
技术讨论