<h2><strong>BubbleSort（冒泡排序）</strong></h2>    <p>定义：在同一个数组中，从数组第一个数开始，相邻两个数进行比较，按照小左大右或者大右小左的顺序，依次循环遍历，进行排序！</p>    <pre>  <code class="language-cpp">void BubbleSort(int *arr,int Length)  {      int i = 0;      int j = 1;      int sys = 0;      for (i = 0; i < Length-1; i++)      {          for (j = 0; j < Length-i-1; j++)          {              if (arr[j]>arr[j+1])              {                  arr[j] = arr[j]^arr[j+1];                  arr[j+1] = arr[j]^arr[j+1];                  arr[j] = arr[j]^arr[j+1];              }            }          sys++;      }        return ;  }</code></pre>    <h3><strong>改进版冒泡排序</strong></h3>    <p>在原有的基础上，我们添加了标记！记录了最后一次交换的位置！</p>    <p>如5，1，4，6，3，2，7，8，9。最后一次交换的位置在2处，并且设定我们每次循环的到2，不对7，8，9</p>    <p>进行比较，节省我们运算的效率！</p>    <p>冒泡排序是对 <strong>全部已经排好</strong> 序列排序最快的</p>    <pre>  <code class="language-cpp">void BetterBubbleSort(int *arr,int Length)  {      int i = 0;      int j = 1;      int pmark;      int sys = 0;      for (; i < Length-1; i++)      {          pmark = 0;          for (j = 0; j < Length-i-1; j++)          {              if (arr[j]>arr[j+1])              {                  arr[j] = arr[j]^arr[j+1];                  arr[j+1] = arr[j]^arr[j+1];                  arr[j] = arr[j]^arr[j+1];                  pmark = j+1;              }            }            i == Length - pmark - 1;          sys++;      }        return ;  }</code></pre>    <h3>不带中间变量实现两个相同类型不同值变量间的互换</h3>    <ol>     <li>加减法</li>    </ol>    <pre>  <code class="language-cpp">int a = 5;  int b = 3;  a = a+b;  b = a-b;  a = a-b;</code></pre>    <ol>     <li>异或^</li>    </ol>    <pre>  <code class="language-cpp">int a = 5;  int b = 3;  a = a^b;  b = a^b;  a = a^b;</code></pre>    <p>ps:若对于 *a ， *b 值进行交换， *a ， *b 不能指向同一块地址空间！</p>    <h2><strong>SelectSort选择排序</strong></h2>    <p>首先，用第一个数去和所有数进行比较，选出其中最小的数，放在第一位，在用第二个数去和全部数进行比较，最小的放在第二位，依次循环遍历！</p>    <pre>  <code class="language-cpp">void SelectSort(int *Arr,int nLength)  {      int i = 0;      int j = 1;      int min = 0;      for (i = 0; i < nLength; i++)      {          for (j = i; j < nLength-1; j++)          {              if (Arr[i] > Arr[j])              {                  Arr[j] = Arr[j]^Arr[i];                  Arr[i] = Arr[j]^Arr[i];                  Arr[j] = Arr[j]^Arr[i];              }          }      }  }</code></pre>    <p>代码优化：把每次都交换的位置，换成比较完之后，有一个int记下来，不用每次比较完进行交换，而是最后直接用记录的数组下标进行交换！</p>    <h2><strong>InsertSort插入排序</strong></h2>    <p>把当前数组分成两部分，第一部分有序，第二部分无序，将无序数组依次插入有序数组里去！</p>    <p>例如数组：10，20，3，8，55.用一个temp保存无序数组第一个</p>    <p>适合场景：每个元素距离其最终位置不远时，我们选择插入排序。</p>    <ol>     <li>首先把10当成有序数组的最后一位，20当成无序数组的第一位，20和10比较，20比10大不移动。</li>     <li>之后用无序数组向后移动一位，变成3，3和20比较，比20小，把3放10和20中间，在用3和10比，比10小，放10前面。</li>     <li>此时有序最后一位仍是20，用8再去和前面几位有序数组进行比较，一次循环遍历！</li>    </ol>    <pre>  <code class="language-cpp">void InsertSort(int arr[],int nLength)  {      int j;//有序数组的最后位置      int i;//无序数组的第一个      int temp;        if(arr == NULL || nLength <=0)return;        for(i = 1;i<nLength;i++)      {          j = i-1;          temp = arr[i]; //保存无序数组的第一个            //进行比较          while(temp < arr[j] && j >=0)          {              //将前一个元素向后移动               arr[j+1] = arr[j];              j--;          }            //将元素放入其对应位置          arr[j+1] = temp;      }    }</code></pre>    <h2><strong>快排</strong></h2>    <p>快排的优点：是 <strong>比较次数最少</strong> 的排序！</p>    <h3><strong>挖坑填补法</strong></h3>    <p>例如数组： <strong> <em>7</em> </strong> ，2，8，4，3，5。我们用temp标记7</p>    <ol>     <li>我们将第一数7当标准值，此时相当于7是一个坑（用粗斜体标记），然后我们从后面依次找比标准值7小的数，<br> 第一个5就比7小，我们将5放到7的坑里。数组变成5，2，8，4，3， <strong> <em>7</em> </strong> ，这是坑变成最后位数！</li>     <li>然后我们在前面找一个比标准值大的数，第3个数8比标准值大，这是我们将8填到数7的坑里！这是数组变成了：<br> 5，2， <strong> <em>7</em> </strong> ，4，3，8，我们对已经操作的数，不再进行考虑比较！</li>     <li>这时我们在从前面开始找一个数比标准值小的数3，填坑。数组变成了：2，3，4， <strong> <em>7</em> </strong> ，8，此时前面和后面的数，<br> 皆比标准值小和大！</li>     <li>标准值前面的数我们看做一个区域，标准值后面的数我们看成一个区域。依次递归循环此区域。</li>    </ol>    <pre>  <code class="language-cpp">//挖坑填补法   int Sort(int arr[],int nLow,int nHigh)  {      int temp ;      temp = arr[nLow]; //保存标准值        while(nLow < nHigh)      {          //从后向前找比标准值小的          while( nLow < nHigh)          {              if(arr[nHigh] > temp)              {                  nHigh--;              }                //小的放前面              else              {                  arr[nLow] = arr[nHigh];                  nLow++;                  break;              }          }            //从前往后找比标准值大的          while(  nLow < nHigh)          {              if(arr[nLow] < temp)              {              nLow++;              }              //大的放后面              else              {                  arr[nHigh] = arr[nLow];                  nHigh--;                  break;              }          }      }        //填坑      arr[nLow] = temp;      return nLow;  }  void QuickSort(int arr[],int nLow,int nHigh)  {      int nIndex;      if(arr == NULL )return;      if(nLow < nHigh)      {          //找到标准值位置          nIndex = Sort(arr,nLow,nHigh);            //根据标准值将当前数组分割成两部分          Sort(arr,nLow,nIndex-1);          Sort(arr,nIndex+1,nHigh);      }  }</code></pre>    <h3><strong>区间（域）分割法</strong></h3>    <p>快排的一种，比挖坑填补法快！类似与挖坑填补法，是其优化升级版吧！</p>    <p>例如，数组：7，5，4，3，6</p>    <ol>     <li>我们选最后一个数6作为标准值，有两个标记，一个是循环标记I，一个是区域标记s。s= i - 1<br> s用红体标记，i用粗斜体标记！s， <strong> <em>7</em> </strong> ，5，4，3，6</li>     <li>用数6去和第一个数7比较，比标准值大， <strong> 7 </strong> , <strong> <em>5</em> </strong> ,4，3，6，则将遍历元素移动到下一处，比标准值6小，<br> 则将数5和7交换， <strong> 5 </strong> ， <strong>7</strong> ，4，3，6。</li>     <li>将遍历指针指下一处， <strong> 5 </strong> ，7， <strong>4</strong> ，3，6，比标准值小，将4和第二个数交换。5， <strong> 4 </strong> ， <strong>7</strong> ，3，6<br> 移动遍历指针，5， <strong> 4 </strong> ，7， <strong>3</strong> ，6</li>     <li>比标准值小，将3和第三个数交换。5，4， <strong> 3 </strong> ， <strong>7</strong> ，6，移动遍历指针。5，4， <strong> 3 </strong> ，7， <strong>6</strong></li>     <li>这时遍历结束，判断++s与i是否相等，若不等，5，4，3， <strong> 7 </strong> ， <strong>6</strong> ，数组[s]与数组[i]交换。</li>     <li>5，4，3， <strong> 6 </strong> ， <strong>7</strong> ，此时标准值6前小后大，递归遍历！</li>    </ol>    <pre>  <code class="language-cpp">//区间分割法  int Sort(int arr[],int nLow,int nHigh)  {      int nSmall;//小区间的右边界      nSmall = nLow-1;      for(nLow;nLow < nHigh;nLow++)      {          //和标准值进行比较          if(arr[nLow] < arr[nHigh])          {              //扩张小区间              if(++nSmall != nLow)              {                  arr[nSmall] = arr[nSmall] ^ arr[nLow];                  arr[nLow] = arr[nSmall] ^ arr[nLow];                  arr[nSmall] = arr[nSmall] ^ arr[nLow];              }          }      }        //标准值放入对应位置      if(++nSmall != nHigh)      {          arr[nSmall] = arr[nHigh] ^ arr[nSmall];          arr[nHigh] = arr[nHigh] ^ arr[nSmall];          arr[nSmall] = arr[nHigh] ^ arr[nSmall];      }        return nSmall;  }    void QuickSort(int arr[],int nLow,int nHigh)  {      int nIndex;      if(arr == NULL )return;      if(nLow < nHigh)      {          //找到标准值位置          nIndex = Sort(arr,nLow,nHigh);            //根据标准值将当前数组分割成两部分          QuickSort(arr,nLow,nIndex-1);          QuickSort(arr,nIndex+1,nHigh);      }  }</code></pre>    <h3><strong>快排区间分割优化</strong></h3>    <p>若我们选择的标准值恰好是最小值或者最大值，这是快排发生交换的次数最多，如果我们在选择下标的时候进行优化，</p>    <p>我们用随机数选择3个下标，之后选其中位数，会最大限度的减少极值下标的可能！</p>    <pre>  <code class="language-cpp">//找中间值下标  int GetIndex(int arr[],int nLow,int nHigh)  {      int a,b,c;      srand(time(NULL));        //随机出三个在下标范围之内的下标      a = rand()%(nHigh-nLow+1) + nLow;      b = rand()%(nHigh-nLow+1) + nLow;      c = rand()%(nHigh-nLow+1) + nLow;        //找到三个的中间值      if(arr[a] > arr[b])      {          if(arr[b] > arr[c])              return b;          else          {              if(arr[a] < arr[c])                  return a;              else                  return c;          }              }      else      {          if(arr[a] > arr[c])              return a;          else          {              if(arr[b] < arr[c])                  return b;              else                  return c;          }      }  }    //区间分割法  int Sort(int arr[],int nLow,int nHigh)  {      int nSmall;//小区间的右边界      int nIndex;      nSmall = nLow-1;        //降低标准值是最大最小值得概率      nIndex = GetIndex(arr,nLow,nHigh);      if(nIndex != nHigh)      {          arr[nIndex] = arr[nIndex] ^ arr[nHigh];          arr[nHigh] = arr[nIndex] ^ arr[nHigh];          arr[nIndex] = arr[nIndex] ^ arr[nHigh];      }        for(nLow;nLow < nHigh;nLow++)      {          //和标准值进行比较          if(arr[nLow] < arr[nHigh])          {              //扩张小区间              if(++nSmall != nLow)              {                  arr[nSmall] = arr[nSmall] ^ arr[nLow];                  arr[nLow] = arr[nSmall] ^ arr[nLow];                  arr[nSmall] = arr[nSmall] ^ arr[nLow];              }          }      }        //标准值放入对应位置      if(++nSmall != nHigh)      {          arr[nSmall] = arr[nHigh] ^ arr[nSmall];          arr[nHigh] = arr[nHigh] ^ arr[nSmall];          arr[nSmall] = arr[nHigh] ^ arr[nSmall];      }        return nSmall;  }    void QuickSort(int arr[],int nLow,int nHigh)  {      int nIndex;      if(arr == NULL )return;      if(nLow < nHigh)      {          //找到标准值位置          nIndex = Sort(arr,nLow,nHigh);            //根据标准值将当前数组分割成两部分          QuickSort(arr,nLow,nIndex-1);          QuickSort(arr,nIndex+1,nHigh);      }  }</code></pre>    <h3><strong>快排终极优化</strong></h3>    <p>如果数量过少时，直接采用插入排序！</p>    <h2><strong>CountSort计数排序</strong></h2>    <p>基于 <strong>非比较</strong> 排序</p>    <p>适用场景：数据分配非常密集的时候！</p>    <p>例如数组：2，1，3，1，2，2，3，4</p>    <ol>     <li>首先在数组中找到最大值和最小值。</li>     <li>然后申请一个max-min+1的数组空间。</li>     <li>遍历数组，如第一个数2，就在申请的数组空间下标为2-最小值的位置+1。<br> 相当于在申请的数组第2个位置，计数加一，每次遇到相同的值都加一。</li>     <li>相当于在申请的数组空间对应下标对应着参数数组中的值，记录其出现的次数。</li>     <li>遍历申请的数组空间，对应着下标将值依次存入参数数组。</li>    </ol>    <pre>  <code class="language-cpp">void CountSort(int arr[],int nLength)  {      int *pCount = NULL;      int i;      int j;      int nMin,nMax;        if(arr == NULL || nLength <=0)return;        //找最大值和最小值      nMax = arr[0];      nMin = arr[0];      for(i = 1;i<nLength;i++)      {          if(arr[i] > nMax)          {              nMax = arr[i];          }          if(arr[i] < nMin)          {              nMin = arr[i];          }      }      //开辟计数数组      pCount = (int *)malloc(sizeof(int ) * (nMax-nMin+1));      memset(pCount,0,sizeof(int ) * (nMax-nMin+1));      //计数      for(i = 0;i<nLength;i++)      {          pCount[arr[i]-nMin]++;      }      //放回原数组      j = 0;      for(i = 0;i< nMax-nMin+1;i++)      {          while(pCount[i] != 0)          {              arr[j] = i+nMin;              j++;              pCount[i]--;          }      }  }</code></pre>    <h2><strong>ShellSort希尔排序</strong></h2>    <p>插入排序的优化，按步长进行分组，然后在组内进行插入排序，然后在二分法步长，重复此过程。（ps:不一定要二分步长）</p>    <p>使用场景：数据少的时候！</p>    <p>例如：35，5，9，12，21，8，7，4，13，25，21，14，长度，n</p>    <ol>     <li>第一次：$ gap=\displaystyle\frac{n}{2}=6 $，也就是说差6为一组，35和7一组，5和4，9和13，12和25，21和21，8和14。<br> 每组内进行插入排序，所以35和7互换位置，5和3互换位置。数组：7，4，9，12，21，8，33，5，13，25，21，14</li>     <li>第二次：$ gap=\displaystyle\frac{gap}{2}=3 $，差3为一组，7，12，33，25一组，4，21，5，21一组，9，8，13，14一组。每组内进行插入排序，25和33换，31和5换。数组：7，4，8，12，5，9，25，21，13，33，21，14</li>     <li>第三次：$ gap=\displaystyle\frac{gap}{2}=1 $向下取整。所以直接对整个数组进行一次插入排序。</li>     <li>总结：每次进行组内的插入排序，都是为了让元素距其最终位置更近一步！</li>    </ol>    <pre>  <code class="language-cpp">void ShellSort(int arr[],int nLength)  {      int gap;      int i; //小组      int j;//插入排序      int k;      int temp;//保存无序数组的第一个        if(arr == NULL || nLength <=0)return;        //定步长      for(gap = nLength/2 ; gap >0 ; gap/=2)      {          //按照步长分组          for(i = 0;i<gap;i++)          {              //各组内部插入排序              for(j = i+gap;j<nLength;j+=gap)              {                  k = j - gap; //有序数组的最后一个                  temp = arr[j]; //无序数组的第一个                    while(arr[k] > temp && k >=i)                  {                      arr[k +gap] = arr[k];                      k-=gap;                  }                  arr[k+gap] = temp;              }          }      }  }</code></pre>    <h3><strong>希尔排序的优化</strong></h3>    <p>分组时，让各组一起进行插入排序，都只进行一次，然后循环进行，代码看起来简洁，但是实际耗时基本相同！</p>    <pre>  <code class="language-cpp">void ShellSort2(int arr[],int nLength)  {      int gap;      int i; //小组      int j;//插入排序      int k;      int temp;//保存无序数组的第一个        if(arr == NULL || nLength <=0)return;        //定步长      for(gap = nLength/2 ; gap >0 ; gap/=2)      {          for(i = gap;i<nLength;i++)          {              //各组内部插入排序                  k = i - gap; //有序数组的最后一个                  temp = arr[i]; //无序数组的第一个                    while(arr[k] > temp && k >=0)                  {                      arr[k +gap] = arr[k];                      k-=gap;                  }                  arr[k+gap] = temp;          }      }  }</code></pre>    <h2><strong>MergeSort归并排序</strong></h2>    <p>先拆分再合并。有2路，3路，5路等，这里用2路作为举例说明。先将数组按照二分法（2路）进行递归拆分，</p>    <p>拆分到每个块里只剩一个元素，然后和相邻元素进行比较排序合并，在比较在合并。</p>    <h3>流程</h3>    <p><img src="https://simg.open-open.com/show/cee70d84cc3ad6132896fd36eff1baac.jpg"></p>    <p> </p>    <pre>  <code class="language-cpp">void Merge(int arr[],int nLow,int nHigh)  {      int nBegin1;      int nEnd1;      int nBegin2;      int nEnd2;      int *pTemp = NULL;      int i;        nBegin1 = nLow;      nEnd1 = (nLow+nHigh)/2;      nBegin2 = nEnd1+1;      nEnd2 = nHigh;        pTemp = (int *)malloc(sizeof(int ) *(nHigh-nLow+1));        //合并      i = 0;      while(nBegin1 <=nEnd1 && nBegin2 <= nEnd2)      {          if(arr[nBegin1] < arr[nBegin2])          {              pTemp[i] = arr[nBegin1];              nBegin1++;          }          else          {              pTemp[i] = arr[nBegin2];              nBegin2++;              }          i++;      }        //将有剩余的数组元素放入临时数组      while(nBegin1 <= nEnd1)      {          pTemp[i] = arr[nBegin1];          i++;          nBegin1++;      }        while(nBegin2 <= nEnd2)      {          pTemp[i] = arr[nBegin2];          i++;          nBegin2++;      }        //将临时数组元素放回原数组      for(i = 0;i < nHigh-nLow +1;i++ )      {          arr[i+nLow] = pTemp[i];      }        //释放      free(pTemp);      pTemp = NULL;    }    void MergeSort(int arr[],int nLow,int nHigh)  {      int nMid;      if(arr == NULL )return;        //两路归并      nMid = (nLow + nHigh)/2;        if(nLow < nHigh)      {          //先拆分           MergeSort(arr,nLow,nMid);          MergeSort(arr,nMid+1,nHigh);            //合并          Merge(arr,nLow,nHigh);      }  }</code></pre>    <h2><strong>HeapSort堆排序</strong></h2>    <p>堆排序是顺序储存，分为大根堆（大堆）和小根堆（小堆）。</p>    <p>大堆：父亲结点一定是三个结点最大的！</p>    <p>小堆：父亲结点一定是三个结点最小的！</p>    <p>并且左右儿子结点并没有什么大小顺序关系，我们只是把这个顺序存储的结构看作是二叉树的结构，</p>    <p>我们仅仅是看作二叉树的形式，实际上也是在数组进行操作，并且根据完全 二叉树性质(第5条) 来进行排序，对此我们要先掌握二叉树的基本知识。</p>    <p>适用场景：在n个元素里找前几个最大的或最小的，我们用堆，并且找大的用小堆，找小的用大堆。</p>    <p>例如：一个数组｛10，2，7，4，6，12，11，9，8｝</p>    <p><img src="https://simg.open-open.com/show/7292e124d8ec77774f6e9681a9dcef9c.jpg"></p>    <ol>     <li>首先数组按照二叉树的形势，我们只是按照二叉树对应的性质来将数组假想成二叉树的样子（并没有真正的改变数组的结构）。</li>     <li>我们按照图2的方式，从下往上从右往左的调整结点的位置，使其遵循大堆的特点！</li>     <li>图三是我们第一次调整好成大堆的样子。</li>     <li>图四我们将堆顶和数组最后一个元素对换。</li>     <li>然后重新按照前面的步骤调整成大堆，最后我们二叉树的第一个结点就是最大的数，依次类推。 二叉树链接</li>    </ol>    <h3><strong>堆排序类型题</strong></h3>    <p>类型题小结：</p>    <ol>     <li>在一个数组中找出前4个最大的数？<br> 答：首先我们想到的是用小堆，我们建立一个只有四个结点的小堆(图在下面)，将数组元素一次放入小堆，并调整成小堆，这是用数组第五元素和堆顶元素比较，若比堆顶元素大的话，则把堆顶元素放入小堆，并移走小堆的最后一个元素（左边最下面），循环完数组小堆里的数就是前4大的！</li>     <li>在50亿个数里找出前50大？<br> 答：还是用小堆，建50个结点，将数据根据内存容量分流，依次按流通过小堆，每个流里选出前50大的，最后在整合到一起，在选出前50的数？</li>     <li>在一个数据流中找到中位数？数据流：一直不间断提供数据，随时提供，不是一个固定的数组。<br> 建立一个大堆和小堆，将数据丢入大堆，并且调整大堆，把大堆堆顶扔小堆里，当来数据的时候，调整小堆，把小堆堆顶放大堆里，来数据时，放入大堆并调整大堆，把大堆堆顶放入小堆里。依次循环过程。此时，小堆堆顶是较大数里最小的，大堆堆顶是比较小数里最大的。若数据的个数为奇数时，小堆堆顶是其中位数。当数据的个数为偶数时，小堆堆顶和大堆堆顶的和除2是其中位数。</li>    </ol>    <p style="text-align:center"><img src="https://simg.open-open.com/show/4c5b686a01a5370f53b7a8df0a7a1a14.jpg"></p>    <h3><strong>堆排序代码</strong></h3>    <pre>  <code class="language-cpp">#define nLeft nRootID*2+1  #define nRight nRootID*2+2    void Adjust2(int arr[],int nLength,int nRootID)  {      int nMax;        //在有孩子的情况下  假设左孩子是大的          for(nMax = nLeft;nLeft < nLength;nMax = nLeft /*下一次继续假设左孩子是最大的8*/)      {          //两个孩子          if(nRight < nLength)          {              //右孩子大                if(arr[nMax] < arr[nRight])              {                  nMax = nRight;              }          }            //大的  和父亲比较  大  则交换          if(arr[nMax] > arr[nRootID])          {              arr[nMax] = arr[nRootID] ^ arr[nMax];              arr[nRootID] = arr[nRootID] ^ arr[nMax];              arr[nMax] = arr[nRootID] ^ arr[nMax];                nRootID = nMax;          }          else          {              break;          }      }  }    void HeapSort(int arr[],int nLength)  {      int i;      if(arr == NULL || nLength <=0)return;      //建初始堆      for(i = nLength/2-1;i>=0;i--)      {          Adjust2(arr,nLength,i);      }      //排序      for(i = nLength-1;i>0;i--)      {          //最大值放后面          arr[i] = arr[i] ^ arr[0];          arr[0] = arr[i] ^ arr[0];          arr[i] = arr[i] ^ arr[0];            //调整根节点          Adjust2(arr,i,0);      }  }</code></pre>    <p> </p>    <p>来自：http://www.jianshu.com/p/a1bfc6114022</p>    <p> </p>