排序算法-选择排序
选择排序（Selection sort）是一种不稳定的排序方法。时间复杂度O(n^2)。遍历整个数组，找到最小的与数组第一个数交换位置，第一个数有序。然后再遍历剩下待排序的数中找出最小的，与第二个位置交换，也就是已排序的末尾。 直到最后一个元素。
一. c语言版
【原版】
/*
选择排序 时间复杂度O(n^2)
不稳定的排序方法:
序列5 8 5 2 9
我们知道第一遍选择第1个元素5会和2交换，那么原序列中两个5的相对前后顺序就被破坏了；
思路：
遍历整个数组，找到最小的与数组第一个数交换位置，第一个数有序
然后再遍历剩下待排序的数中找出最小的，与第二个位置交换，也就是已排序的末尾。
直到最后一个元素。
*/
void SelectSort1(int *arr,int len)
{
int i=0,j=0;
int minIndex=0;
for(i=0;i<len-1;i++){//因为前面都排有序了，那么最后一个也就不用循环，自然有序。
minIndex = i;//默认当前最小
for(j=i+1;j<len;j++){
if(arr[minIndex]>arr[j]){
minIndex = j;//找到最小值的下标
}
}
if(minIndex!=i){//如果最小值不是当前值，那么就不用交换了
swap(&arr[minIndex],&arr[i]);
}
}
}
【优化】
/*
【选择排序优化】
思路：我们上面的每次循环的时候只是找了一个数最小值放左边，那么同时我们也可以找到最大值放右边。
例如8 4 6 2 第一次循环找到最大值 最小值的位置
maxIndex = 0 left=0 right=3
minIndex = 3
=>先交换最小值
因为左指针left正好等于maxIndex
swap(&arr[minIndex],&arr[left]); 也就是 2 4 6 8 这个时候
那么这个时候0的位置 成了最小的值 改变了maxIndex 最大值跑到3的位置
所以我们做一个 maxIndex = minIndex=3;
然后再交换右边最大的数
swap(&arr[maxIndex],&arr[right]);
*/
void SelectSort2(int *arr,int len)
{
int left=0,right=0,cur=0;//左指针 右指针 当前值
int minIndex=0,maxIndex=0;
for(left=0,right=len-1; left<right ; left++,right--){
minIndex = left;//最小值 下标
maxIndex = right;//最大值 下标
for(cur=left; cur<=right ; cur++){
if(arr[minIndex]>arr[cur]){
minIndex=cur;
}
if(arr[maxIndex]<arr[cur]){
maxIndex=cur;
}
}
//将最小值交换到左边
swap(&arr[minIndex],&arr[left]);
//因为先交换的最小值位置，但是也要考虑到最大值在最小值left的位置。
if(left == maxIndex){
maxIndex = minIndex;
}
swap(&arr[maxIndex],&arr[right]);
}
} 【完整代码】
#include<stdio.h>
#include<string.h>
#include<time.h>
#define MAX 100000
void SelectSort1(int *arr,int len);//选择排序 每次循环找出最小值
void SelectSort2(int *arr,int len);//选择排序 优化 同时找到最大值最小值
void getRandArray(int *arr,int len,int Range); //随机生成一个长度为n一维数组 随机数的范围在[0 Range)
void getNearRandArray(int *arr,int len,int times);//随机生成一个部分有序的数组 长度为n 无序交换次数
void swap(int *a,int *b); //交换两个变量
void dump(int arr[],int len); //打印
int main()
{
clock_t begin , end;
double time;
int arr1[MAX],arr2[MAX];
getRandArray(arr1,MAX,100);
//getNearRandArray(arr1,MAX,5);
memcpy(arr2,arr1,sizeof(arr1));
begin = clock();//开始记录
SelectSort1(arr1,MAX);
end = clock(); //结束记录
time = (double)(end - begin)/CLOCKS_PER_SEC;
printf("【 array length is %d 】【选择排序1】【cost time is %lf 】\n",MAX,time);
begin = clock();//开始记录
SelectSort2(arr2,MAX);
end = clock(); //结束记录
time = (double)(end - begin)/CLOCKS_PER_SEC;
printf("【 array length is %d 】【选择排序2】【cost time is %lf 】\n",MAX,time);
return 0;
}
/**
选择排序 时间复杂度O(n^2)
不稳定的排序方法:
序列5 8 5 2 9
我们知道第一遍选择第1个元素5会和2交换，那么原序列中两个5的相对前后顺序就被破坏了；
思路：
遍历整个数组，找到最小的与数组第一个数交换位置，第一个数有序
然后再遍历剩下待排序的数中找出最小的，与第二个位置交换，也就是已排序的末尾。
直到最后一个元素。
*/
void SelectSort1(int *arr,int len)
{
int i=0,j=0;
int minIndex=0;
for(i=0;i<len-1;i++){//因为前面都排有序了，那么最后一个也就不用循环，自然有序。
minIndex = i;//默认当前最小
for(j=i+1;j<len;j++){
if(arr[minIndex]>arr[j]){
minIndex = j;//找到最小值的下标
}
}
if(minIndex!=i){//如果最小值不是当前值，那么就不用交换了
swap(&arr[minIndex],&arr[i]);
}
}
}
/*
【选择排序优化】
思路：我们上面的每次循环的时候只是找了一个数最小值放左边，那么同时我们也可以找到最大值放右边。
例如8 4 6 2 第一次循环找到最大值 最小值的位置
maxIndex = 0 left=0 right=3
minIndex = 3
=>先交换最小值
因为左指针left正好等于maxIndex
swap(&arr[minIndex],&arr[left]); 也就是 2 4 6 8 这个时候
那么这个时候0的位置 成了最小的值 改变了maxIndex 最大值跑到3的位置
所以我们做一个 maxIndex = minIndex=3;
然后再交换右边最大的数
swap(&arr[maxIndex],&arr[right]);
*/
void SelectSort2(int *arr,int len)
{
int left=0,right=0,cur=0;//左指针 右指针 当前值
int minIndex=0,maxIndex=0;
for(left=0,right=len-1; left<right ; left++,right--){
minIndex = left;//最小值 下标
maxIndex = right;//最大值 下标
for(cur=left; cur<=right ; cur++){
if(arr[minIndex]>arr[cur]){
minIndex=cur;
}
if(arr[maxIndex]<arr[cur]){
maxIndex=cur;
}
}
//将最小值交换到左边
swap(&arr[minIndex],&arr[left]);
//因为先交换的最小值位置，但是也要考虑到最大值在最小值left的位置。
if(left == maxIndex){
maxIndex = minIndex;
}
swap(&arr[maxIndex],&arr[right]);
}
}
//随机生成一个数组
void getRandArray(int *arr,int len,int Range)
{
srand(time(NULL));//设置随机种子
int i = 0;
for (i=0; i<len; i++){
arr[i] = rand() % Range;//范围在Range以内
}
}
//随机生成一个比较有序的数组 先有序，然后随机交换位置
void getNearRandArray(int *arr,int len,int times)
{
int i = 0;
for(i;i<len;i++){//先构造一个有序的数组
arr[i] = i;
}
srand(time(NULL));//设置种子
for(i=0;i<times;i++){//尽量有序 循环交换多少次
int posx = rand()%(len-1);//在[1,len-1]上随机位置
int posy = rand()%(len-1);
swap(&arr[posx],&arr[posy]);//随机交换两个位置的数
}
}
//交换两个值 利用指针交换位置
void swap(int *a,int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
//打印输出数组
void dump(int *arr,int len)
{
int i=0;
for(i=0;i<len;i++)
printf("%d ",arr[i]);
printf("\n");//换行
} 二. PHP版
【选择排序1】
/**
选择排序
时间复杂度 O(n^2) 不稳定性
param array $arr 要排序的数组
param int $len 数组的长度
return array $arr 排好序的数组
**/
public function selectSort1($arr,$len)
{
$i=$j=$minIndex=0;
for($i=0;$i<$len-1;$i++){
$minIndex = $i;
for($j=$i+1;$j<$len;$j++){
($arr[$minIndex]>$arr[$j]) && ($minIndex = $j);
}
if($minIndex!=$i){
$this->swap($arr[$minIndex],$arr[$i]);//交换最小值
}
}
return $arr;
}【选择排序2】
/**
* 选择排序优化
**/
public function selectSort2($arr,$len)
{
$left=$right=$cur=0;
$minIndex=$maxIndex=0;
for($left=0,$right=$len-1; $left<$right; $left++,$right--){
$minIndex = $left;//最小值的下标
$maxIndex = $right;//最大值的下表
for($cur=$left; $cur<=$right; $cur++){
($arr[$minIndex]>$arr[$cur]) && ($minIndex=$cur);
($arr[$maxIndex]<$arr[$cur]) && ($maxIndex=$cur);
}
//交换最小值
$this->swap($arr[$minIndex],$arr[$left]);
if($left == $maxIndex){//放置 最大值就在left的位置上。
$maxIndex = $minIndex;
}
$this->swap($arr[$maxIndex],$arr[$right]);
}
return $arr;
}【完整代码】
<?php
//选择排序
class Select
{
const MIN = 0;
const MAX = 1000;//设置随机数的范围
private $len = 10;//默认构造的数组长度
private $times= 10;//无序交换次数
public $arr = [];//要排序的数组
public $out = [];//排好序的数组
public function __construct($len=0,$times=0,$min=Select::MIN,$max=Select::MAX)
{
$this->len = empty($len) ? $this->len:$len;//判断要生成数组的长度
$this->times= empty($times) ? $this->times:$times; //无序交换次数
$this->arr = $this->getRandArray($this->len,$min,$max);//生成无序数组
//$this->arr = $this->getNearRandArray($this->len,$this->times,$min,$max);//生成相对有序数组
echo '数组长度:',$len,'<br/>';
echo '随机数范围:[',$min,',',$max,']','<br/>';
//echo '无序交换次数:',$times,'<br/>';
$stime=microtime(true);
$this->out = $this->selectSort1($this->arr,$this->len);//调用选择排序1
$etime=microtime(true);
$total=$etime-$stime;
echo "<br />[选择排序]执行时间为：{$total} 秒<br/>";
$stime=microtime(true);
$this->out = $this->selectSort2($this->arr,$this->len);//调用选择排序2
$etime=microtime(true);
$total=$etime-$stime;
echo "<br />[优化选择排序]执行时间为：{$total} 秒<br/>";
// var_dump($this->arr,$this->out);
}
/**
选择排序
时间复杂度 O(n^2) 不稳定性
param array $arr 要排序的数组
param int $len 数组的长度
return array $arr 排好序的数组
**/
public function selectSort1($arr,$len)
{
$i=$j=$minIndex=0;
for($i=0;$i<$len-1;$i++){
$minIndex = $i;
for($j=$i+1;$j<$len;$j++){
($arr[$minIndex]>$arr[$j]) && ($minIndex = $j);
}
if($minIndex!=$i){
$this->swap($arr[$minIndex],$arr[$i]);//交换最小值
}
}
return $arr;
}
/**
* 选择排序优化
**/
public function selectSort2($arr,$len)
{
$left=$right=$cur=0;
$minIndex=$maxIndex=0;
for($left=0,$right=$len-1; $left<$right; $left++,$right--){
$minIndex = $left;//最小值的下标
$maxIndex = $right;//最大值的下表
for($cur=$left; $cur<=$right; $cur++){
($arr[$minIndex]>$arr[$cur]) && ($minIndex=$cur);
($arr[$maxIndex]<$arr[$cur]) && ($maxIndex=$cur);
}
//交换最小值
$this->swap($arr[$minIndex],$arr[$left]);
if($left == $maxIndex){//放置 最大值就在left的位置上。
$maxIndex = $minIndex;
}
$this->swap($arr[$maxIndex],$arr[$right]);
}
return $arr;
}
//交换两个变量
private function swap(&$a,&$b)
{
$temp = 0;//借助第三个变量
$temp = $a;
$a = $b;
$b = $temp;
}
/**
生成部分有序的数组
@params $len 数组长度
@params $times 数组无序交换的次数
@params $min $max 随机数的范围
return array
**/
private function getNearRandArray($len,$times,$min,$max)
{
$arr = [];//生成部分有序的数组
for($i=0; $i<$len; $i++){
$arr[$i] = $i;
}
for($i=0; $i<$times; $i++){//打乱有序 循环交换多少次
$posx = mt_rand($min,$max)%($len-1);//在[1,len-1]上随机位置
$posy = mt_rand($min,$max)%($len-1);
$this->swap($arr[$posx],$arr[$posy]);//随机交换两个位置的数
}
return $arr;
}
/**
生成随机数组
@params $len 随机数组的长度
@params $min $max 随机数的范围
**/
private function getRandArray($len,$min,$max)
{
$arr = [];//生成无序的数组
for($i=0; $i<$len; $i++){
$arr[$i] = mt_rand($min,$max);
}
return $arr;
}
}
new Select(1000,5);//实例化类
投递完美世界等公司6个岗位 >