大数据管理的重要思想和算法总结----排序（上）

void swap(int* x, int* y)//交换函数
{
  int tmp = *x;
  *x = *y;
  *y = tmp;
}
void BubbleSort(int* arr1, int sz)//冒泡排序函数
{
  int j = 0;
  for (j = 0; j < sz; j++)
  {
    int flag = 0;
    int i = 0;
    for (i = 1; i < sz-j; i++)//这里别出错，是sz-j而不是，仅仅小于j,排好一个元素后还得排sz-1个，这个思路别错了
    {
      if (arr1[i] <arr1[i -1])
      {
        swap(&arr1[i], &arr1[i -1]);
        flag = 1;
      }
    }
    if (flag == 0)
    {
      break;
    }
  }
}

void InsertSort(int*arr1,int sz)//直接插入排序函数
{  
     int i = 0;
  for (i = 0; i < sz - 1; i++)
  {
    int end =i;
    int tmp = arr1[end + 1];//要存储即将插入的数据，否则会覆盖，就找不到这个数据了，所以在排列开始前要先把数据存储起来。
    while (end >= 0)
    {
      if (tmp < arr1[end])
      {
        arr1[end + 1] = arr1[end];
      }
      else
      {
        break;//注意这里用break的细节，常规写一个arr1[end+1]=tmp即可，但是倘若是end减到-1的情况跳出循环了，其赋值方式与小于等于是相同的，所以我们不如直接跳出循环写在一起，这个思路很巧妙，要积累。
      }
      end--;//别忘了单趟循环end要--，以保证比较是一直进行的
    }
    arr1[end + 1] = tmp;
  }
}

**1.首先，这不仅仅是直接插入排序或者是冒泡排序的问题，几乎所有的排序都面临控制边界的问题，在直接插入排序也需要控制好边界，对于我这里+1的写法，就要控制其end最多不能超过sz-2,而且要强调，我们这里操作的是下标，而不是里面具体的元素，故我们一定要看好下标的边界在哪里。
                  **2.其次，搞清楚我们的直接插入的逻辑是什么，将一个元素放在当前数组的最后尾部向着头部比较前进，遇到合适的位置就插入进入，这个大思路别错，而且我们操纵的是下标，这个千万要记住别忘了！！！！**
                  **3.掌握一种逻辑方法，即先单趟再多趟的思路，就是先搞清楚我们一次插入的过程是怎样实现的，然后套上一个循环就可以实现整个数据的整体排序了**

void SelectSort(int* arr1, int sz)//直接选择排序函数
//注意：！！！！！我们这里使用优化版本，即每次选出最大和最小的，最大的放在最右边，最小的放在最左边，然后调整数组的范围直到数组结束，但要注意，我们这里要找的是下标而不是里面的具体数值！！！！！
{//必须要强调：直接选择排序对应的不是内部的元素，而是其下标，这个一定要记住！！！！！！！
  int i = 0;
  int left = 0;
  int right= sz - 1;
  while (left < right)//注意循环的条件
  {
       int mini = left;//注意每次都要刷新mini和maxi的初始下标，防止数据被覆盖以及进一步缩小范围至[left+1,right]
     int maxi = right;
    for (i = left+1; i <=right; i++)//遍历的范围也在left到right范围内部，元素范围也从left+1的位置开始到right-1的范围内访问
    {
      if (arr1[i] > arr1[maxi])
      {
        maxi = i;
      }
      if (arr1[i] < arr1[mini])
      {
        mini = i;
      }
    }
    swap(&arr1[left], &arr1[mini]);//注意要交换而不是赋值，这个不要想错了
    if (left == maxi)//倘若为 9 1也就是最大值与left重叠，mini一旦与其交换，下一次maxi就会直接和right交换这样就出错了，所以一旦有这种情况，即left和maxi重叠的情况，则交换完之后，如果left==maxi，则把mini的下标赋给maxi，这样就避免了这种情况的出现
    {
      maxi = mini;
    }
    swap(&arr1[right], &arr1[maxi]);//注意，两个swap谁在前面谁需要调整
    left++;
    right--;
  }
}

void AdjustDown(int* arr1, int sz, int parent)//向下调整函数
{
  int child = parent * 2 + 1;//向下调整要传父亲节点，求出子节点，这样直接就把堆给构建出来了
  while (child < sz)//向下调整是循环，别忘了，这个向下调整写的还是不够好
  {
    if (child + 1 < sz && arr1[child + 1] > arr1[child])//注意。向下调整传父亲节点，向上调整传孩子节点
    {
      child++;
    }
    if (arr1[child] > arr1[parent])
    {
      swap(&arr1[child], &arr1[parent]);
      parent = child;
      child = child * 2 + 1;
    }
    else
    {
      break;
    }
  }
}
void HeapSort(int* arr1, int sz)//堆排序函数,向下调整建堆法,升序向上建大堆
{
  int i = 0;
  for(i = (sz - 1 - 1) / 2; i >= 0; i--)
  {
    AdjustDown(arr1, sz, i);
  }
  int end = sz - 1;
  while (end > 0)
  {
    swap(&arr1[end], &arr1[0]);//别忘了先交换首尾元素，然后找到
    AdjustDown(arr1, end, 0);
    end--;
  }
}

void AdjustDown(int* arr1, int sz, int parent)//向下调整函数
{
  int child = parent * 2 + 1;//向下调整要传父亲节点，求出子节点，这样直接就把堆给构建出来了
  while (child < sz)//向下调整是循环，别忘了，这个向下调整写的还是不够好
  {
    if (child + 1 < sz && arr1[child + 1] > arr1[child])//注意。向下调整传父亲节点，向上调整传孩子节点
    {
      child++;
    }
    if (arr1[child] > arr1[parent])
    {
      swap(&arr1[child], &arr1[parent]);
      parent = child;
      child = child * 2 + 1;
    }
    else
    {
      break;
    }
  }
}

void ShellSort(int* arr1, int sz)//希尔排序函数，希尔排序算法的思路就是：对于数据首先进行一个预处理，将其通过不断削减gap的数值使其逐渐变得有规律，直到最后gap==1的时刻，成为了插入排序，但由于先前的排序铺垫，插入排序只需要调整微小的局部数据即可，故效率很高
{
  //先写常规写法：即分批次希尔排序法，也可以用并序希尔排序法
    int gap = sz;//默认把gap数值从数组的长度开始分组，直到gap变成1
    while (gap > 1)
    {
      gap =gap/ 3+1;//注意，这里的逻辑就是，每一次不断缩减gap的数值使其分组越来越细，当gap等于1时实际上即为插入排序的过程，得到的即为最后的排序，注意，gap过大时有时自己除自己不一定得到1，所以我们人为的补上一个1，保证其最后gap一定会等于1
      //int j = 0;
      //for(j=0;j<gap;j++)
      //{
        int i = 0;//上面的使用了j的是常规的希尔为分列希尔排序，下面我们采用并序希尔排序法，即从0到sz-gap进行插入排序
        for (i = 0; i < sz - gap; i++)//这里便是一个常规的插入排序的过程，只不过插入的间隔是gap，如果是常规算法，这里就是i+=gap,反之连续希尔排序就是i++
        {
          int end = i;
          int tmp = arr1[end + gap];
          while (end >= 0)
          {
            if (tmp < arr1[end])
            {
              arr1[end + gap] = arr1[end];
            }
            else
            {
              break;
            }
            end -= gap;
          }
          arr1[end + gap] = tmp;
        }
      //}
    }
}

void ShellSort(int* arr1, int sz)//希尔排序函数，希尔排序算法的思路就是：对于数据首先进行一个预处理，将其通过不断削减gap的数值使其逐渐变得有规律，直到最后gap==1的时刻，成为了插入排序，但由于先前的排序铺垫，插入排序只需要调整微小的局部数据即可，故效率很高
{
  //先写常规写法：即分批次希尔排序法，也可以用并序希尔排序法
    int gap = sz;//默认把gap数值从数组的长度开始分组，直到gap变成1
    while (gap > 1)
    {
      gap =gap/ 3+1;//注意，这里的逻辑就是，每一次不断缩减gap的数值使其分组越来越细，当gap等于1时实际上即为插入排序的过程，得到的即为最后的排序，注意，gap过大时有时自己除自己不一定得到1，所以我们人为的补上一个1，保证其最后gap一定会等于1
      int j = 0;
      for(j=0;j<gap;j++)
      {
        int i = 0;//上面的使用了j的是常规的希尔为分列希尔排序，下面我们采用并序希尔排序法，即从0到sz-gap进行插入排序
        for (i = j; i < sz - gap; i+=gap)//这里便是一个常规的插入排序的过程，只不过插入的间隔是gap，如果是常规算法，这里就是i+=gap,反之连续希尔排序就是i++
        {
          int end = i;
          int tmp = arr1[end + gap];
          while (end >= 0)
          {
            if (tmp < arr1[end])
            {
              arr1[end + gap] = arr1[end];
            }
            else
            {
              break;
            }
            end -= gap;
          }
          arr1[end + gap] = tmp;
        }
      }
    }
}

// 假设按照升序对array数组中[left, right)区间中的元素进行排序
void QuickSort(int array[], int left, int right) {
 if(right - left <= 1)
 return;
 // 按照基准值对array数组的 [left, right)区间中的元素进行划分
 int div = partion(array, left, right);
 // 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div+1, right)
 // 递归排[left, div)
 QuickSort(array, left, div);
 // 递归排[div+1, right)
 QuickSort(array, div+1, right);
}