xietao3

探索之旅,学习之路

你好,我是谢涛!欢迎来到我的个人主页.
90后代码搬运工,目前就职于上海天天果园,任职iOS高级开发工程师。


算法-选择排序

这几乎是最简单的排序方法…

核心思想

选择排序的思想其实和冒泡排序有点类似,都是在一次排序后把最小的元素放到最前面,或者将最大值放在最后面。但是过程不同,冒泡排序是通过相邻的比较和交换。而选择排序是通过对整体的选择,每一趟从前往后查找出无序区最小值,将最小值交换至无序区最前面的位置。

示例

第一轮过程: 初始化一个minIndex=0,i=0~9,依次将arr[i]与arr[minIndex]进行对比,如果arr[minIndex]的值较小则无操作,如果arr[i]的值较小,则将minIndex=i,意思是目前最小值的位置下标为i,直至这轮结束,minIndex的值则是该组数据无序区最小值的下标,将最小值交换到无序区最前面的位置,此时n=0的位置有序。

选择排序-第一轮 第二轮过程 :i=1~9 查找最小值,对比方式与第一轮一样,找出最小值下标,将最小值交换至n=1的位置,第三轮i=2~9,最小值交换至n=2的位置。

整个循环过程:

原始长度10
100	5	3	11	33	6	8	7	1	3	
第1轮
1	5	3	11	33	6	8	7	100	3	
第2轮
1	3	5	11	33	6	8	7	100	3	
第3轮
1	3	3	11	33	6	8	7	100	5	
第4轮
1	3	3	5	33	6	8	7	100	11	
第5轮
1	3	3	5	6	33	8	7	100	11	
第6轮
1	3	3	5	6	7	8	33	100	11	
第7轮
1	3	3	5	6	7	8	33	100	11	
第8轮
1	3	3	5	6	7	8	11	100	33	
第9轮
1	3	3	5	6	7	8	11	33	100

时间复杂度

选择排序同样需要两轮循环才能完成排序。所以时间复杂度为O ( n^2)。

C语言代码

#pragma mark - 选择排序
void pickSort(int arr[] ,int len) {
    printf("原始长度%d\n",len);
    printfArr(arr, len);
    for (int i = 0; i < len-1; i++) {
        printf("第%d轮\n",i+1);
        int minLocation = i;
        for (int j = i; j < len-1; j++) {
            int preNum = arr[minLocation];
            int nexNum = arr[j+1];
            
            if (preNum>nexNum) {
                minLocation = j+1;
            }
        }
        if (minLocation != i) {
            int temp = arr[i];
            arr[i] = arr[minLocation];
            arr[minLocation] = temp;
        }
        printfArr(arr, len);
    }
}

结语

这个比冒泡简单,你觉得呢?

最近的文章

算法-插入排序

生活总是充满了惊喜,无论是惊还是喜。核心思想有一个已经有序的数据序列,要求在这个已经排好的数据序列中插入一个数,但要求插入后此数据序列仍然有序,这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序。示例对于长度为n的数组,全部完成排序需要经过n-1轮的查找,首先我们从第二个数开始,向前比较,如果比前面的数小,则继续向前对比,直至遇见大于前置位数字时,或者到了数组的最前...…

继续阅读
更早的文章

算法-冒泡排序

貌似是程序员基础,我一个高级开发竟然只会冒泡(羞耻ing…)前言之前买了剑指offer,一直搁那里没怎么看,现在挑灯夜读挤出点时间学习下,在这之前还是得先把基础给打牢,这里先介绍算法入门-冒泡排序。核心思想冒泡排序的核心思想就是通过与相邻元素的比较和交换,把小的数交换到最前面。因为这个过程类似于水泡向上升一样,因此被命名为冒泡排序。示例 第一轮过程: i=0~9;依次进行arr[i]与arr[i+1]对比;arr[i]小则不交换,arr[i+1]小则与arr[i]交换位置,由于100...…

继续阅读