十大排序大总结

   <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>