[数据结构与算法]排序算法介绍及学习卡壳点理解

该文章主要内容是排序算法的基本实现原理、代码实现及我学习过程遇到的卡壳（例如为什么要一开始用k代替i，而不是直接用i和j交换？为什么是n-1趟？）

一.算法原理：

进行n-1(此时n=4)趟挑选，挑选第i（1<=i<=n-1）趟中最小(最大)的值放到这一趟的首位。

1.为什么n-1趟？

因为每一趟选出一个值排序，到n-1趟时，已经有n-1个值被排好，此时仅剩的一个值也自然而然被排好了，没有其他位置可放。

2. 为什么“挑选这一趟中最小(最大)的值”？

因为当第一趟选出那个值，必然是整个数组最小(最大)的值，同时当它交换到数组首位a[0],所以当第二趟时，无需再与a[0]比较，仅需对a[1]及以后的值进行对比，以此类推第二趟，第三趟……

二.算法正序实现文字叙述：

第一趟：拿a[0]到a[3]做比较，选出a[0]到a[3]最小的放到a[0];

第二趟：拿a[1]到a[3]做比较，选出a[1]到a[3]最小的放到a[1];

第三趟：拿a[2]到a[3]做比较，选出a[2]到a[3]最小的放到a[2];

最后此时a[3]的值正好是数组中最大的。

三.算法正序实现代码叙述：

c++版：

#include<iostream>
using namespace std;

void  selectSort(int*Array,int n);

int main()
{
    int a[10] = { 9,6,3,8,5,2,7,4,1,0 };
    selectSort(a, 10);
    for (int i = 0; i < 10; i++)
    {
        cout << a[i];
    }
}

//排序算法代码
void  selectSort(int*Array,int n) {
    for (int i = 0; i < n; i++)//n-1趟
    {
        int k = i;//该第i趟要从a[i]到a[n-1]进行比较，选出最小，因此先将i的下标赋给k。
        for (int j = i; j < n; j++)//换句话说，就是该趟循环从i至n-1（数组最后一个元素下标）找出最小的值，并将其下标赋给k，则a[k]成为该趟最小一个元素
        {
            if (Array[j] < Array[k])
                k= j;
        }

        int t = Array[k];//让当前最小的a[k]与该趟首位的a[i]交换.
        Array[k] = Array[i];
        Array[i] = t;
    }
}

c语言版：（c++其实是可以兼容c的，可以在.cpp文件里运行c语言）

#include<stdio.h>
void  selectSort(int* Array, int n);

int main()
{
    int a[10] = { 9,6,3,8,5,2,7,4,1,0 };
    selectSort(a, 10);
    for (int i = 0; i < 10; i++)
    {
        printf("%d", a[i]);
    }
}

void  selectSort(int* Array, int n) {
    int i, j, t,k;
    for (i = 0; i < n; i++)//n-1趟
    {
         k = i;//该i第i趟要从a[i]到a[n-1]进行比较，选出最小，因此先将i的下标赋给k。
        for ( j = i; j < n; j++)//换句话说，就是该趟循环中从i至n-1（数组最后一个元素下标）找出最小的值，并将其下标赋给k，则a[k]成为该趟最小一个元素
        {
            if (Array[j] < Array[k])
                k = j;
        }

         t = Array[k];//让当前最小的a[k]与该趟首位的a[i]交换.
        Array[k] = Array[i];
        Array[i] = t;
    }
}

1.为什么弄个k？

我们a[k]存放当前趟最小值，最后与a[i](即每一趟的首位)交换，这样a[i]就获得了该趟最小值，

2.为什么不直接拿 i 和 j 交换？

这样就会在第二层循环里改变i，而我们的代码是在第一层循环改变i的。