排序（二）【数据结构】

简单选择排序（选择排序 不稳定）

核心思想：

每一趟找到待排序序列中最小的值，以及找到待排序序列的第一个值进行交换
（即 每一趟就是找到待排序序列中的最小值，通过交换的方式放到第一个位置上）

特别注意：

代码实现中，本质是要找到他们的位置

时间、空间复杂度

时间复杂度：O(n^2)
空间复杂度：O(1)

代码实现

//选择排序voidSelect_Sort(intarr[],intlen){for(inti=0;i<len-1;i++){intminIndex=i;for(intj=i;j<len;j++){if(arr[j]<arr[minIndex])minIndex=j;}inttmp=arr[i];arr[i]=arr[minIndex];arr[minIndex]=tmp;}}

冒泡排序

核心思想：

每一趟从前向后两两比较，（递增）如果左边大于右边，则交换，反之不交换，当这一趟跑完之后，相当于最大值就被搬运到最后一个位置了

改进：

如何在一趟两两比较完成后就立刻得知其是否已经完全有序？放一个flag=0，若某一趟未交换则标记为1.

代码实现

//冒泡排序voidBubble_Sort(intarr[],intlen){for(inti=0;i<len-1;i++){intflag=0;for(intj=0;j<len-i-1;j++){if(arr[j]>arr[j+1]){inttmp=arr[j];arr[j]=arr[j+1];arr[j+1]=tmp;flag=1;}}if(flag==0)break;}}