鏈懆鎬荤粨 瀛︾敓(鎬荤粨鏈懆宸ヤ綔)

这个星期学习了排序算法（C语言）的相关问题：

1.直接插入排序

基本思想：

在待排序的元素中，假设n-1个元素已经有序，现将第n个元素插入到前面已经排好的序列中，使得前n个元素有序。按照此法对所有元素进行插入，直至整个序列有序。

                              4  6  3  2  1  5 

                              3  4  6  2  1  5                           默认序列的第一个元素有序，则依次将元素

                              2  3  4  6  1  5                           向前插入，直至序列有序。

                              1  2  3  4  6  5

                              1  2  3  4  5  6

插入排序代码：

void InsertSort(int* a, int n)
{
     int i = 0;
     for(i = 0; i < n-1; i++)
      {
          int end = i;
          int tmp = a[end + 1];
          while (end >= 0)
          {
               if(tmp < a[end]
               { 
                    a[end + 1] = a[end];
                    end --
               }
               else
               {
                break;
               }
          }
          a[end + 1] = tmp;
       }
}

  2.选择排序

  基本思想：

        每次从待排序列中选出一个最小值，然后放在序列的起始位置，直到全部待排数据排完即可。

选择排序代码：

//选择排序(一次选一个数)
void SelectSort(int* a, int n)
{
   int i = 0;
   for (i = 0; i < n; i++)//i代表参与该趟选择排序的第一个元素的下标
   {
       int start = i;
       int min = start;//记录最小元素的下标
       while (start < n)
       {
          if (a[start] < a[min])
          min = start;//最小值的下标更新
          start++;
       }
  Swap(&a[i], &a[min]);//最小值与参与该趟选择排序的第一个元素交换位置
    }
}

可以同时取最大的元素和最小的元素，实现代码如下：

//选择排序(一次选两个数)
void SelectSort(int* a, int n)
{
   int left = 0;//记录参与该趟选择排序的第一个元素的下标
   int right = n - 1;//记录参与该趟选择排序的最后一个元素的下标
   while (left < right)
   {
      int minIndex = left;//记录最小元素的下标
      int maxIndex = left;//记录最大元素的下标
      int i = 0;
      //找出最大值及最小值的下标
      for (i = left; i <= right; i++)
      {
          if (a[i] < a[minIndex])
          minIndex = i;
          if (a[i]>a[maxIndex])
          maxIndex = i;
       }
  //将最大值和最小值放在序列开头和末尾
  Swap(&a[minIndex], &a[left]);
  if (left == maxIndex)
  {
      maxIndex = minIndex;//防止最大值位于序列开头，被最小值交换
  }
  Swap(&a[maxIndex], &a[right]);
  left++;
  right--;
   }
}