基础算法(1):排序(1):选择排序

     今天对算法产生了兴趣，开始学习基础算法，比如排序，模拟，贪心，递推等内容，算法是很重要的，它是解决某个问题的特定方法，程序=数据结构+算法，所以对算法的学习是至关重要的，它可以提高程序效率，不同的算法也是有优劣的，如何进行评价，这也是我们需要知道的，我会在学习中穿插这种评价方法，下面让我们看看第一个基础算法排序中的选择排序。

1.选择排序的实现

     选择排序(SelectionSort)算法的工作原理是每一次遍历从待排序的元素中选出最小(或最大)的一个元素，将其放在已经排好序的数列之后，直到全部排好序为止。

     其核心就是选择和交换，流程如下：

      假如给定初始数据 8 4 2 7 3（红色为每次遍历交换的数据）

      第一次排序 2 4 8 7 3

      第二次排序 2 3 8 7 4

      第三次排序 2 3 4 7 8

      首先在未排序序列中找到最小(或最大)元素，放到排序序列的起始位置，然后再从剩余未排序元素中继续寻找最小(或最大)元素，然后放到已排序序列的末尾，直到所有元素全部排好序。

      逻辑是这样：

   (1)第一轮从下标为 1 到下标为 n-1 的元素中选取最小值，若小于第一个数，则交换
   (2)第二轮从下标为 2 到下标为 n-1 的元素中选取最小值，若小于第二个数，则交换
        依次类推下去……

      我们可以再看一个动画演示加深对过程的理解，本图非本人所作，借鉴别人的。

       下面是代码实现：

void selectionSort(int arr[],int len)
{int i,j,min,temp;for(i=0;i<len-1;i++){min=i;//先定义一个最小值对应的下标for(j=i+1;j<len;j++){if(arr[min]>arr[j])//如果大于就更新最小值对应的下标{min=j;}}temp=arr[min];//循环结束，找到本次待排序序列的最小值，和序列首元素进行交换，之后进入下一次循环arr[min]=arr[i];arr[i]=temp;}
}

       或者下面这个版本

void selectSort(int arr[], int n) {if(n==0||n==1)return;int i, j, minIndex;for (int i = 0; i < n - 1; i++) {minIndex = i;//先定义最小值对应的下标for (int j = i + 1; j < n-1; j++){minIndex = arr[j] < arr[minIndex] ? j : minIndex;//如果小于就更新最小值下标}int temp=arr[min];//循环结束，找到本次待排序序列的最小值，和序列首元素进行交换，之后进入下一次循环arr[min]=arr[i];arr[i]=temp;}
}

2.选择排序的时间复杂度

      时间复杂度？这是什么玩意？别搞我啊？可能大家在看到这个词的心理状态是这样的，但你先别急。

2.1 时间复杂度

       时间复杂度是用来评价算法性能的，它是用来方便开发者估算程序的运行时间，我们如何估计程序运行时间呢？我们通常会估计算法的操作单元数量，来代表程序消耗的时间

      假设算法道德问题规模为n，那么操作单元数量就用函数f(n)来表示，随着n的增大，算法执行时间的增长率和f(n)的增长率相同，这就称作算法的时间复杂度，记为O(f(n))。

      大O用来表示上界的，当用它作为算法的最坏情况运行时间的上界，就是对任意数据输入的运行时间的上界。

  2.2 如何描述时间复杂度

     决定使用哪个算法不仅仅要考虑时间复杂度，不是时间复杂越低的越好，要考虑数据规模，如果数据规模很小，甚至可以用O(n^2)的算法比 O(n)的更合适，就像上图中图中 O(5n^2) 和O(100n) 在n小于2的时候 O(5n^2)是更优的，所花费的时间也是最少的。

     那我们为什么在计算时间复杂度的时候要忽略常数项系数呢，也就说O(100n) 就是O(n)的时间复杂度，并且要默认O(n) 优于O(n^2) 呢 ？

     因为大O其实就是数据量级突破一个点且数据量级非常大的情况下所表现出的时间复杂度，也就是刚才说的上界，在这个时候，常数项系数已经不起决定性作用了，所以可以省略。

     例如上图中 20 就是那个点 ，n只要大于20 常数项系数已经不起决定性作用了，其实也包括除最高次数项的其他项。

     所以我们说的时间复杂度都是省略常数项系数的，是因为一般情况下我们都是默认数据规模足够的大，基于这样的事实 我们给出的算法时间复杂的的一个排行如下所示：

     O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)

     这里只是大概列出概念，后面会专门写一篇来讲这方面的问题。

2.3 选择排序的时间复杂度

     从上面的代码我们可以知道选择排序套用了两个循环：

for(i=0;i<n-1;i++)
{for(j=i+1;j<n;j++){}}

     很显然问题规模是n，问题规模就是需要解决问题处理数据量的大小，显然是处理n个元素的排序问题，规模为n。

     当i=0时，下面内循环比较n-1次，每次i+1下面内循环比较n-i次，因此总共循环次数(操作单元数量)为(n-1)+(n-2)+......+2+1=n^2/2，舍去最高项系数，时间复杂度为O(n^2)。

3.leetcode题目

3.1 颜色分类

void sortColors(int* nums, int numsSize) {int i,j,min,temp;for(i=0;i<numsSize-1;i++){min=i;for(j=i+1;j<numsSize;j++){if(nums[min]>nums[j]){min=j;}}temp=nums[min];nums[min]=nums[i];nums[i]=temp;}
}

      这个没什么好说的，就是排序，太水了，模板题。

3.2 至少是其他数字两倍的最大数

int dominantIndex(int* nums, int numsSize) {if(numsSize==1)return 0;int max=0;for(int i=0;i<numsSize;i++){if(nums[max]<nums[i])max=i;}int minindex=0;for(int i=0;i<numsSize-1;i++){minindex=i;for(int j=i+1;j<numsSize;j++){minindex=nums[j]<nums[minindex]?j:minindex;}if(i!=minindex){int temp=nums[i];nums[i]=nums[minindex];nums[minindex]=temp;}}if(nums[numsSize-1]>=2*nums[numsSize-2])return max;else return -1;
}

      这个题也不难，关键在于我们要先记录最大数对应的下标，因为我们排序后会破坏原来的顺序，再就是我们只需要判断排序后最后一个数是不是至少是前一个数的两倍，如果这个满足，那这个最大数也必然是其他是的至少两倍。

3.3 判断能否形成等差数列

bool canMakeArithmeticProgression(int* arr, int arrSize) {for(int i=0;i<n;i++){int minindex=i;for(int j=i+1;j<n;j++){minindex=nums[j]<nums[minindex]?j:minindex;}int temp=nums[i];nums[i]=nums[minindex];nums[minindex]=temp;}int d=arr[1]-arr[0];for(int i=2;i<arrSize;i++){if((arr[i]-arr[i-1])!=d)return false;}return true;
}

    这个题就是先排序，这样我们就可以很容易的判断，先假定公差为前两个数之差，如果遍历后面相邻两个数之差等于该公差，那说明是等差数列，否则不是。