【排序算法】C语言实现选择排序与冒泡排序

关于冒泡排序，其实我们就关注两件事
1.需要几趟冒泡
对于一个有n个元素的数组，我们需要 n-1 趟冒泡
很好理解，比如：3 2 1这三个数
一趟冒泡会把3移到末尾变成 2 1 3
第二趟就会把2移到3的前一位变成 1 2 3这时数组已经有序了
2.一趟冒泡进行几次比较
对于有n个元素的数组来说：
第一次冒泡，范围是下标0 ~ n-1，就比较n-1次
第二次冒泡，范围是下标0 ~ n-2，就比较n-2次
第三次冒泡，范围是下标0 ~ n-3，就比较n-3次
 … … … …

//交换方法
void swap(int a[], int x, int y)
{
  int tmp = a[x];
  a[x] = a[y];
  a[y] = tmp;
}
//经典冒泡排序
void BubbleSort(int a[], int sz)//sz表示传入数组的大小
{
  //end表示需要进行几趟冒泡
  for (int end = sz - 1; end > 0;end--)
  {
    //同时end从sz-1开始，作为比较次数限定第二个for循环的范围
    //每一趟冒泡都是从下标 0和1  1和2  2和3 ……比较
    //second代表每次比较的第二个数，也就是0和1的1,1和2的2
    //所以second从1开始
    for (int second = 1; second <= end; second++)
    {
      //当第一个数大于第二个数就交换
      if (a[second - 1] > a[second])
      {
        //交换函数，传入数组名和需要交换的两个数的下标
        swap(a, second, second - 1);
      }
    }
  }
}

void BubbleSort(int a[], int sz)
{
  for (int end = sz - 1; end > 0;end--)
  {
    int flag = 0;//增加一个flag变量，判断是否数组已有序
    for (int second = 1; second <= end; second++)
    {
      if (a[second - 1] > a[second])
      {
        swap(a, second, second - 1);
        flag = 1;
      }
    }
    //flag为0说明没进行交换，没交换就说明每个数的前一个数不大于它
    //说明数组已有序跳出循环
    if (flag == 0)
      break;
  }
}

同样选择排序我们也只关心两件事
1.进行几次找最小值
这与冒泡类似，一个有n个元素的数组进行，n-1次选择
2.每次寻找最小值的范围
对于有n个元素的数组来说：
对于有n个元素的数组来说：
第一次选择，范围是下标0 ~ n-1
第二次选择，范围是下标1 ~ n-1
第三次选择，范围是下标2 ~ n-1
…………

//交换方法
void swap(int a[], int x, int y)
{
  int tmp = a[x];
  a[x] = a[y];
  a[y] = tmp;
}
//选择排序
void SelectSort(int a[],int sz)//sz数组元素个数
{
  int first = 0;//控制找最小值，并且是每一次要找最小值的范围的第一个元素的下标
  for (first = 0; first < sz - 1; first++)
  {
    int end = sz - 1;//控制遍历最小值的范围，并且从后遍历数组
    int min = first;//min记录最小值的下标
    while(end > first)
    {
      //如果以end为下标的元素比以min为下标的元素小，min就记录该数的下标
      min = a[min] > a[end] ? end : min;
      end--;
    }
    swap(a, first, min);//每次找到的最小数与开始位置交换
  }
}