选择排序

开始慢慢复习算法，巩固基础。

从最简单的排序开始，主要是理解排序的思想，之前看了很多次书，从来没有实际过，发现结果都忘记了。

可以用扑克牌来想象排序的过程，只不过有些操作对于计算机来说要复杂一些，比如：

找出队伍中的最小值一眼就看出来了，但是计算机要挨个遍历。
将几找已排序的手牌向后移动，计算机需要逐个移动个体。

先记录一下选择排序。

排序思想：
假设目标是从小到大。在一列无序的队伍中，首先遍历找到最小值，然后与第一个值交换位置，这样第一个值就是最小了。然后从第二个值开始遍历最小值，找到后与第二值交换位置，如此一直遍历到最后一个值。
所以需要两层循环，第一层循环用来保证遍历的次数，也就是元素的个数-1，第二层循环用来遍历得到最小值。
第0次要遍历N个数
第1次要遍历N-1个数
。。。
第n次要遍历N-n个数

如果从整理一手扑克牌的角度来看，此算法也够SB的了，因为即使是 234567891 这样的顺序，和 987654321 这样的顺序，需要的时间是一样的。

具体的代码如下：

 // Defines the entry point for the console application.   
//   
  
  
#include "stdafx.h"   
#include "windows.h"   
#include "time.h"   
  
  
const int N = 10;  
int O = 0;  
  
  
int* GenRandom()  
{  
       srand( (unsigned)time( NULL ) );  
  
  
       int* a = new int[N];  
       for (int i = 0; i < N; i++)  
       {  
           a[i] = rand() * rand();  
       }  
       return a;  
}  
  
  
void swap(int& a, int& b)  
{  
       int temp = 0;  
       temp = a;  
       a = b;  
       b = temp;  
}  
  
  
//small -> large   
void SelectionSort(int* ua)  
{  
       //round times，遍历N次   
       for (int i = 0; i < N-1; i++)  
       {  
              //printf("round %d \r\n", i);   
              //for (int i = 0; i < N; i++)   
              //{   
              //     printf("a[%d]=%d \r\n",i, *(ua+i));   
              //}   
  
  
              int nMinIndex = i;//最小值的索引   
//每次确定一个值，从第一个值开始。。。第二次从第二个值开始   
              for (int j = i + 1; j < N; j++)  
              {  
                     if( ua[nMinIndex] >= ua[j] )  
                     {  
                           nMinIndex = j;  
                     }  
                     O++;  
              }  
              swap(ua[i], ua[nMinIndex] );  
       }  
}  
  
  
SYSTEMTIME StartTime = {0};  
FILETIME StartFileTime = {0};  
SYSTEMTIME EndTime= {0};  
FILETIME SEndFileTime= {0};  
  
  
int _tmain(int argc, _TCHAR* argv[])  
{  
       int* a = GenRandom();  
       GetSystemTime(&StartTime);  
       printf("timeBefore %d:%d:%d \r\n", StartTime.wMinute, StartTime.wSecond, StartTime.wMilliseconds);  
  
  
       SelectionSort(a);  
  
  
       GetSystemTime(&EndTime);  
       printf("timeAfter %d:%d:%d \r\n", EndTime.wMinute, EndTime.wSecond, EndTime.wMilliseconds);  
       printf("times %d \r\n", O);  
       return 0;  
}  

// Defines the entry point for the console application.
//


#include "stdafx.h"
#include "windows.h"
#include "time.h"


const int N = 10;
int O = 0;


int* GenRandom()
{
       srand( (unsigned)time( NULL ) );


       int* a = new int[N];
       for (int i = 0; i < N; i++)
       {
           a[i] = rand() * rand();
       }
       return a;
}


void swap(int& a, int& b)
{
       int temp = 0;
       temp = a;
       a = b;
       b = temp;
}


//small -> large
void SelectionSort(int* ua)
{
       //round times，遍历N次
       for (int i = 0; i < N-1; i++)
       {
              //printf("round %d \r\n", i);
              //for (int i = 0; i < N; i++)
              //{
              //     printf("a[%d]=%d \r\n",i, *(ua+i));
              //}


              int nMinIndex = i;//最小值的索引
//每次确定一个值，从第一个值开始。。。第二次从第二个值开始
              for (int j = i + 1; j < N; j++)
              {
                     if( ua[nMinIndex] >= ua[j] )
                     {
                           nMinIndex = j;
                     }
                     O++;
              }
              swap(ua[i], ua[nMinIndex] );
       }
}


SYSTEMTIME StartTime = {0};
FILETIME StartFileTime = {0};
SYSTEMTIME EndTime= {0};
FILETIME SEndFileTime= {0};


int _tmain(int argc, _TCHAR* argv[])
{
       int* a = GenRandom();
       GetSystemTime(&StartTime);
       printf("timeBefore %d:%d:%d \r\n", StartTime.wMinute, StartTime.wSecond, StartTime.wMilliseconds);


       SelectionSort(a);


       GetSystemTime(&EndTime);
       printf("timeAfter %d:%d:%d \r\n", EndTime.wMinute, EndTime.wSecond, EndTime.wMilliseconds);
       printf("times %d \r\n", O);
       return 0;
}

补充：综合编程 , 其他综合 ,