【排序算法之选择排序】

默认的排序都是升序队列，但是也有降序队列，看君需要

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法（比如序列[5， 5， 3]第一次就将第一个[5]与[3]交换，导致第一个5挪动到第二个5后面）。

 

选择排序的思想非常直接，不是要排序么？那好，我就从所有序列中先找到最小的，然后放到第一个位置。之后再看剩余元素中最小的，放到第二个位置……以此类推，就可以完成整个的排序工作了。可以很清楚的发现，选择排序是固定位置，找元素。相比于插入排序的固定元素找位置，是两种思维方式。

 

for(int i=0; i<v.size(); i++){

int min = v[i]; 

int temp;

int index = i;

for(int j=i+1;j<v.size();j++){

   if(v[j] < min){ 

min = v[j]; 

index = j;

   }       

}       

 

temp = v[i]; 

v[i] = min;

v[index]= temp;

}

 

选择排序核心思想：

每次从无序队列之中，选择一个最值来排序，默认第一个元素为最值，拿他与待排序队列中的所有值进行比较，选择真实的最值，填充在队列的首位，这样待排序队列中元素就减少一个，然后从待排序队列中选择第二个最值，这样待排序队列中元素就减少二个.....直到待排序元素为空为止.

 

 

插入排序核心思想：

插入排序核心思想来自现实生活中的插队，现实生活中，你插过队吧。你肯定首先要从队列中扫描找到一个熟人，关系比较近的人，然后插入到他的前面，你如果插入到熟人的后面，你懂得，别人会翻你白眼，但是插队不文明，劝君少做......但是计算机中是寻找一个最值插入到他的后面（保证前面比他小后面比他大，或者反过来前面比你大，后面比你小）。你从队首开始扫描还是队尾开始扫描是无所谓的，随着有序队列的增长，后续待排元素扫描的成本会增长，插队的过程代价会增高