美文网首页程序员读书
【数据结构】选择排序

【数据结构】选择排序

作者: 星际编码 | 来源:发表于2019-04-15 09:00 被阅读0次

默认数组为升序

选择排序:
一趟选择排序的操作为:通过n-1次关键字间的比较,从n-i个记录中选出关键字最小的记录,并和第i(0<=i<n)个记录进行交换。
一共需要进行n-1趟选择排序。

排序的数组为{6, 2, 8, 1, 4, 9, 3, 0, 5, 7};

选择排序代码

#include<iostream>
using namespace std;
swap( int array[], int j ) {    //交换方法 
    int temp = array[j];
    array[j] = array[j-1];
    array[j-1] = temp;
}
void insertSort( int array[] ) {//选择排序方法 
    for( int i = 0; i < 9; i++ ) {
        for( int j = i+1; j > 0; j-- ) {
            if( array[j] < array[j-1] ) {
                swap( array, j );
            }
            else {
                break;
            }
        }
    }
} 
int main() {
    int array[] = {6, 2, 8, 1, 4, 9, 3, 0, 5, 7};
    insertSort( array );        //调用选择排序方法 
    for( int i = 0; i < 10; i++ ) {
        cout << "array[" << i << "] = " << array[i] << endl;
    }
}

选择排序原理

如,对数组{6, 2, 8, 1, 4, 9}6个数字进行排序

数组 第一趟循环

找出最小的数字array[3]=0,与array[0]=6进行交换。确定了第一小的数字“1”

第二趟循环

此时,最小的数字即array[1]本身。确定了第二小的数字“2

第三趟循环

此时,找出最小的数字array[4]=4,与array[2]=8进行交换。确定了第三小的数字“4”

第四趟循环

此时,最小的数字即array[3]本身。确定了第四小的数字“6”

最后两次循环

确定后最后两位数字,第五小的数字“8”,以及最大的数字“9”

根据上图可知,每一趟循环可以确定一个最小的数值

再看如下例子

比较次数 6 2 8 1 4 9 3 0 5 7
1 0 2 8 1 4 9 3 6 5 7
2 0 1 8 2 4 9 3 6 5 7
3 0 1 2 8 4 9 3 6 5 7
4 0 1 2 3 4 9 8 6 5 7
5 0 1 2 3 4 9 8 6 5 7
6 0 1 2 3 4 5 8 6 9 7
7 0 1 2 3 4 5 6 8 9 7
8 0 1 2 3 4 5 6 7 9 8
9 0 1 2 3 4 5 6 7 8 9

{\text{选择排序表格}}

  1. 在第一层循环中:
    首先min=array[i],mini=i;
    1. min和array[1]比较,min>array[1],则:min=array[1],mini=1;
    2. min和array[2]比较,min<array[2],则无需改变min与mini;
    3. min和array[3]比较,min>array[3],则:min=array[3],mini=3;
      ……
    4. min和array[9]比较,min>array[9],则无需改变min与mini;
  2. 第一层循环排序的结果为:
    0, 2, 8, 1, 4, 9, 3, 6, 5, 7
  3. 同理,第二层排序的结果
    0, 1, 8, 2, 4, 9, 3, 6, 5, 7
  4. 第三层排序结果:
    0, 1, 2, 8, 4, 9, 3, 6, 5, 7
    ……
  5. 第八层排序结果:
    0, 1, 2, 3, 4, 5, 6, 7, 9, 8
  6. 第九层排序结果:
    0, 1, 2, 3, 4, 5, 6, 7, 8, 9

综上可得:
升序排序中,外层循环每循环一次,都会将最小的数字与当前位的数字进行交换。

如果大家有什么问题,可以在评论区中向我提问。
今天更新的是选择排序,后天我会更新“插入排序”,是三大排序中难度相对较大的。希望我的文章对大家有一定的帮助!

相关文章

  • C语言:关于数据的几种排序算法

    数据结构的排序算法有很多种。其中,快速排序、希尔排序、堆排序、直接选择排序不是稳定的排序算法;基数排序、冒泡排序、...

  • 排序

    一、选择排序 1.堆排序 定义:堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序可参考http...

  • 021-数据结构与算法-排序

    基础方法或者数据结构的定义: 冒泡排序 选择排序 插入排序 希尔排序 希尔排序思想: 希尔排序是把记录按下标的一定...

  • 玩转算法面试:(三)LeetCode数组类问题

    数组中的问题其实最常见。 排序:选择排序;插入排序;归并排序;快速排序查找:二分查找法数据结构:栈;队列;堆…… ...

  • 算法(3)- 数组

    数组中的问题其实最常见如:排序(选择排序、插入排序、归并排序、快速排序)、查找(二分查找法)、数据结构(栈、队列、...

  • 算法与数据结构路线图

    学习算法与数据结构,深刻理解计算机科学 排序算法:插入、冒泡、选择、希尔、快速、归并、堆排序、计数排序、桶排序、基...

  • 2019-07-16

    数据结构排序 单链表上的简单选择排序 判断一个堆是不是小顶堆

  • 堆排序

    预备知识 堆排序 堆排序(heap sort)是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的...

  • 常见排序

    近来要校招了,基本的排序还是需要掌握的。数据结构,算法永远都是写出好程序的基本功。 冒泡排序 选择排序 插入排序 ...

  • 2018-06-30

    排序算法之堆排序 堆排序是利用堆的数据结构而设计的一种排序算法,堆排序是一种选择排序。可以利用数组的特点快速定位制...

网友评论

    本文标题:【数据结构】选择排序

    本文链接:https://www.haomeiwen.com/subject/ccujwqtx.html