排序函数的算法（day12）

今天尝试了三种数字的排序法。目的为

1）熟悉数组的操作

2）熟悉循环

笔者是做嵌入式的，不想再算法上做过多探究，自身水平和专业也不允许深入太多。现在直接给出三种排序函数。

1.插值排序

void insort(int s[], int n)
{
  int i, j;
  for (i = 2; i <=n  ; i++)
  {
    s[0] = s[i];
    j = i - 1;
    while (s[0] < s[j])
    {
      s[j + 1] = s[j];
      j--;
    }
    s[j + 1] = s[0];
  }
}

int main()
{
  int arr[11], i;
  printf("请输入10个数字\n");
  for (i = 1; i <= 10; i++)
  {
    scanf("%d", &arr[i]);
  }
  for (i = 1; i <= 10; i++)
  {
    printf("%5d", arr[i]);
  }
  insort(arr, i - 1);
  printf("\n排序结果：\n");
  for (i = 1; i < 11; i++)
  {
    printf("%5d", arr[i]);
  }
  return 0;
}

其实现逻辑如下：

1）取数组的S0为警戒哨，S0为空

2）从数组的第二个元素开始排序（第一个元素无法比较）,将两两比较的后一位作为警戒哨的值

S2[（S1，S2）,S3 , S4.........)]

3)将S1,S2排序（警戒哨保留为S2的值）

4）进入下一组排序

S3[S1，（S2 , S3） , S4.........)]

将S2,S3排序，通过while循环，用保留的S3的值，将S3插入S1,S2,S3存储区域中合适的位置。

5）进入下一组排序

S4[S1，S2 , （S3 , S4）.........)]

将S3,S4排序，通过while循环，用保留的S4的值，将S4插入S1,S2,S3，S4存储区域中合适的位置。

。。。。。。。

2.冒泡排序

void bubble_sort(int arr[], int sz)
{
  int i = 0;
  for (i = 0; i < sz - 1; i++)
  {
    int j = 0;
    for (j = 0; j < sz - 1 - i; j++)
    {
      if (arr[j] > arr[j + 1])
      {
        int tmp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = tmp;
      }
    }

  }
  
  int main()
{
    int arr[] = { 2,8,9,4,5,3,1,7 };
    int i = 0;
    int sz = sizeof(arr) / sizeof(arr[0]);
    bubble_sort(arr, sz);
    for (i = 0; i <= sz; i++)
    {
        printf("%d", arr[i]);
    }
    return 0;
}

其实现逻辑如下：

实例

3.快速排序（两者结合的改良）

void qusort(int s[], int start, int end)
{
  int i, j;
  i = start;
  j = end;
  s[0] = s[start];
  while (i < j)
  {
    while (i < j && s[0] < s[j])
      j--;
    if (i < j)
    {
      s[i] = s[j];
      i++;
    }
    while (i < j && s[i] <= s[0])
      i++;
    if (i < j)
    {
      s[j] = s[i];
      j--;
    }
  }
  s[i] = s[0];
  if (start < i)
    qusort(s, start, j - 1);
  if (i < end)
    qusort(s, j + 1, end);
}


int main()
{
  int arr[11], i;
  printf("请输入10个数：\n");
  for (i = 1; i <= 10; i++)
  {
    scanf("%d", &arr[i]);
  }
  qusort(arr, 1, 10);
  printf("排序后的顺序:\n");
  for (i = 1; i <= 10; i++)
  {
    printf("%5d", arr[i]);
  }
}

实例

使用了递归，代码效率提升，但是代码复杂。