直至整个排好顺序

c语言排序算法计算

一 理论

一、稳定排序和非稳定排序
简单地说正是具备相等的数经过某种排序方法后,仍可以维持它们在排序此前的相对次序,我们就说那种排序方法是稳定的。反之,正是非稳定的。
 比如:一组数排序前是a一,a二,a三,a四,a5,个中a二=a肆,经过某种排序后为a一,a二,a四,a三,a5,
则大家说那种排序是政通人和的,因为a二排序前在a四的前面,排序后它还是在a4的前头。假若变成a一,a4,a二,a叁,a五就不是稳定的了。

2、内排序和向外排水序

 在排序进程中,全部要求排序的数都在内部存储器,并在内部存款和储蓄器中调整它们的积存顺序,称为内排序;在排序进度中,只有部分数被调入内部存款和储蓄器,并借助内存调整数在外部存款和储蓄器中的存放顺序排序方法称为向外排水序。

三、算法的小运复杂度和空中复杂度

 所谓算法的时辰复杂度,是指执行算法所急需的持筹握算工作量。
 二个算法的空中复杂度,一般是指执行这一个算法所急需的内部存款和储蓄器空间。

图片 1

排序算法 平均时间复杂度 空间复杂度 稳定性
插入排序 O(n^2) O(1) 稳定
希尔排序 O(n^1.5) O(1) 不稳定
选择排序 O(n²) O(1) 不稳定
堆排序 O(N*logN) O(1) 不稳定
冒泡排序 O(n^2) O(1) 稳定
快速排序 O(N*logN) O(N*logN) 不稳定
归并排序 O(N*logN) O(1) 稳定

贰 排序算法介绍

 功能:选料排序

算法1:插入排序

 输入:数组名称(也正是数组首地址)、数组桐月素个数

介绍:

 

  选拔排序(Selection
sort)是壹种简单直观的排序算法。它的干活规律如下。首先在未排序类别中找到最小成分,存放到排序连串的起第二人置,然后,再从剩余未排序成分中继续查找最小元素,然后嵌入排序类别末尾。以此类推,直到全体因素均排序实现。

步骤:

 
 每一次:i与别的的比,选小的,记录下标;

             
一趟相比截至时:(交流地点)放在sorted队列的漏洞。

  起首下一趟。**n-1趟**

排序效果:

图片 2

     

 

 

 

 

 

 

插入排序算法.png

选用排序是不稳定的。算法复杂度O(n二)–[n的平方]

[cpp] view plaincopy
void select_sort(int *x, int n)  
{  
   int i, j, min, t;  
  for (i=0; i<n-1; i++) /*要选择的次数:0~n-2共n-1次*/  
   {  
      min = i; /*假设当前下标为i的数最小,比较后再调整*/  
//s1 每一趟,找到最小数的下标,并记录下来
      for (j=i+1; j<n; j++)/*循环找出最小的数的下标是哪个*/

      {  
         if (*(x+j) < *(x+min))  
         {     
            min = j; /*如果后面的数比前面的小,则记下它的下标*/  
         }  
      }    
//s2:把最下坐标对应的数,放在排好的队列的尾巴。

     if (min != i) /*如果min在循环中改变了,就需要交换数据*/  
       {  
         t = *(x+i);  
         *(x+i) = *(x+min);  
         *(x+min) = t;  
       }  
   }  
}  

================================================
 功能:冒泡排序  输入:数组名称(相当于数组首地址)、数组夷则素个数 ================================================

   介绍:

  冒泡排序(Bubble
Sort,湖南译为:泡沫排序或气泡排序)是1种简单的排序算法。它再一次地拜会过要排序的数列,一遍相比较三个元素,若是他们的逐一错误就把他们调换过来。走访数列的做事是再一次地展开直到未有再必要交换,相当于说该数列已经排序达成。这几个算法的名字由来是因为越小的要素会经过交流慢慢“浮”到数列的上方。

步骤:

 每一趟:相邻的比,选大的泡(换地点)往上冒,跑到了最上面(此时终结了)。起初下壹趟n-1趟。

  1. 比较相邻的因素。借使第三个比首个大,就交换他们七个。
  2. 对每1对左近元素作同样的行事,从开始首先对到最终的末梢一对。在这或多或少,最后的要素应该会是最大的数。
  3. 本着具有的要素重复以上的步调,除了最终四个。
  4. 持续每回对越来越少的成分重复上面的步调,直到未有任何一对数字须求相比。

排序效果:

 

图片 3

 

 

 

 

 

 

 

 

冒泡排序是平稳的。算法时间复杂度O(n2)–[n的平方] =====================================================

void BubbleSort(int *array,int n)    
{    
    int temp;    
    for (int i=n-1;i>0;i--)    
    {    
        for (int j=0;j<i;j++)    
        {    
            if (*(array+j)>*(array+j+1))    
            {    
                temp=*(array+j);    
                *(array+j)=*(array+j+1);    
                *(array+j+1)=temp;    
            }    
        }    
    }    
}  

================================================
 功能:**火速排序

插入排序(Insertion
Sort)在要排序的一组数中,假定前n-1个数已经排好序,今后将第n个数插到前方的雷打不动数列中,使得那n个数也是排好顺序的。如此反复循环,直到①切排好顺序。

 输入:数组名称(也便是数组首地址)、数组中起止成分的下标**

介绍:

     非常快排序是对冒泡排序的一种精神立异。它的骨干思虑是因此壹趟扫描后,使得排序系列的长度能相当大地减小。在冒泡排序中,3回扫描只好有限支撑最大数值的数移到正确地点,而待排序种类的长短也许只 减弱一。飞快排序通过壹趟扫描,就能确定保证有些数(以它为基准点吧) 的左侧各数都比它小,左边各数都比它大。然后又用同一的办法处理 它左右两边的数,直到基准点的左右唯有2个成分结束。 
     显然连忙排序能够用递归达成,当然也足以用栈消除递归达成。上面包车型大巴 函数是用递归完结的,有趣味的爱侣能够改成非递归的。

步骤:

  • 从数列中挑出2个要素,称为 “基准”(pivot),
  • 再也排序数列,全数因素比基准值小的摆放在基准后面,全部因素比基准值大的摆在基准的末尾(相同的数可以到任一边)。在这么些分区退出之后,该规则就处于数列的中游地方。那么些称呼分区(partition)操作。
  • 递归地(recursive)把小于基准值成分的子数列和超越基准值成分的子数列排序。

    排序效果: 

图片 4

 

 

 

 

 

 

 

飞快排序是不稳定的。最精良图景算法时间复杂度O(nlog2n),最坏O(n二)

=====================================================

void quick_sort(int *x, int low, int high)  
{  
   int i, j, t;  
   if (low < high)/*要排序的元素起止下标,保证小的放在左边,大的放在右边。以下标为low的元素为基准点*/   {  
      i = low;  
      j = high;  
      t = *(x+low); /*暂存基准点的数*/  
      while (i<j) /*循环扫描*/  
      {  
//比t大的,在右边:j--,一个个的比较来。 
        while (i<j && *(x+j)>t) /*在右边的只要比基准点大仍放在右边*/  
         {  
          j--;               /*前移一个位置*/  
         }  
         //比t小:替换基准点的数*(x+i)=*(x+j),i++。  t没变的啊还是t=*(x+low)
         if (i<j)   
         {  
          *(x+i) = *(x+j);  /*上面的循环退出:即出现比基准点小的数,替换基准点的数*/  
          i++;              /*后移一个位置,并以此为基准点*/  
         }  
//比t小的数放在左边,i++;一个个来比较。

         while (i<j && *(x+i)<=t) /*在左边的只要小于等于基准点仍放在左边*/  
         {  
          i++; /*后移一个位置*/  
         }  
      //否则:比t大,放在右边的*(x+j)=*(x+i),j--;
         if (i<j)  
         {  
            *(x+j) = *(x+i); /*上面的循环退出:即出现比基准点大的数,放到右边*/  
            j--; /*前移一个位置*/  
         }  
      }  

     *(x+i) = t; /*一遍扫描完后,放到适当位置*/  
     quick_sort(x,low,i-1);  /*对基准点左边的数再执行快速排序*/  
     quick_sort(x,i+1,high);  /*对基准点右边的数再执行快速排序*/  
   }  
}  

 

================================================
 功能:直接插入排序  输入:数组名称(也正是数组首地址)、数组否月素个数 ================================================
算法思想简单描述:

     在要排序的一组数中,倘使后边(n-一)
[n>=2]个数已经是排好顺序的,今后要把第n个数插到前面包车型客车稳步数中,使得那n个数 也是排好顺序的。如此频仍循环,直到①切排好顺序。

  • 从第多少个因素发轫,该因素得以认为已经被排序
  • 取出下三个要素,在曾经排序的要素连串中从后迈入扫描
  • 万1该因素(已排序)大于新因素,将该因素移到下一个人置
  • 重新步骤3,直到找到已排序的因素小于可能等于新因素的地方
  • 将新成分插入到该职位中
  • 再次步骤二

     直接插入排序是安静的。算法时间复杂度O(n2)–[n的平方] =====================================================

void insert_sort(int *x, int n)  
{  
 int i, j, t;  
 for (i=1; i<n; i++) /*要选择的次数:1~n-1共n-1次*/  
 {  
  /* 
   暂存下标为i的数。注意:下标从1开始,原因就是开始时 
   第一个数即下标为0的数,前面没有任何数,单单一个,认为 
   它是排好顺序的。 
  */  
  t=*(x+i);  
  for (j=i-1; j>=0 && t<*(x+j); j--) /*注意:j=i-1,j--,这里就是下标为i的数,在它前面有序列中找插入位置。*/  
  {  
   *(x+j+1) = *(x+j); /*如果满足条件就往后挪。最坏的情况就是t比下标为0的数都小,它要放在最前面,j==-1,退出循环*/  
  }  
  *(x+j+1) = t; /*找到下标为i的数的放置位置*/  
 }  
}  

希尔排序算法思想简单描述:
     在直接插入排序算法中,每便插入三个数,使有系列只扩张二个节点,并且对插入下贰个数未有提供任何赞助。要是比较相隔较中远距离(称为增量)的数,使得数移动时能跨过四个成分,则展开二遍比较就大概撤除八个因素调换。D.L.shell于一九伍玖年在以他名字命名的排序算法中落到实处 了那壹考虑。

算法先将要排序的1组数按某些增量d分成若干组,每组中 记录的下标相差d.对每组中全体成分实行排序,然后再用一个较小的增量 对它举行,在每组中再举办排序。当增量减到一时,整个要排序的数被分为 一组,排序实现。
 
     下边包车型客车函数是2个希尔排序算法的多个贯彻,初次取类别的2/4为增量,今后每一回减半,直到增量为一。

图片 5

[cpp] view plaincopy
void shell_sort(int *x, int n)  
{  
 int h, j, k, t;  
 for (h=n/2; h>0; h=h/2) /*控制增量*/  
 {  
  for (j=h; j<n; j++) /*这个实际上就是上面的直接插入排序*/  
  {  
   t = *(x+j);  
   for (k=j-h; (k>=0 && t<*(x+k)); k-=h)  
   {  
    *(x+k+h) = *(x+k);  
   }  
   *(x+k+h) = t;  
  }  
 }  
}  

================================================
 功能:堆排序  输入:数组名称(相当于数组首地址)、数组兰月素个数 ====================================================
算法思想简单描述:

    堆排序是壹种树形选用排序,是对一分区直属机关接大选择排序的管事改正。 堆的定义如下:具有n个成分的队列(h一,h二,…,hn),当且仅当满足(hi>=h贰i,hi>=二i+1)或(hi<=h二i,hi<=二i+1)(i=一,2,…,n/二)时名叫堆。在此地只谈谈满足前者条件的堆。

     由堆的概念能够观察,堆顶成分(即首先个因素)必为最大项。完全二叉树能够很直观地代表堆的布局。堆顶为根,其余为左子树、右子树。起先时把要排序的数的行列看作是一棵顺序存款和储蓄的二叉树,调整它们的仓库储存顺序,使之成为三个堆,那时堆的根节点的数最大。然后将根节点与堆的末尾三个节点沟通。然后对前边(n-1)个数重新调整使之变成堆。依此类推,直到唯有多个节点的堆,并对它们作交流,最终收获有n个节点的有序类别。

     从算法描述来看,堆排序要求五个经过,一是确立堆,二是堆顶与堆的结尾3个要素
 沟通地点。所以堆排序有多少个函数组成。1是建堆的渗漏函数,2是数次调用渗透函数
 完成排序的函数。

     堆排序是不平静的。算法时间复杂度O(nlog2n)。

图片 6

 

===================================================

 功能:渗透建堆
 输入:数组名称(也就是数组首地址)、参与建堆元素的个数、从第几个元素开始
====================================================

[cpp] view plaincopy
void sift(int *x, int n, int s)  
{  
 int t, k, j;  
 t = *(x+s); /*暂存开始元素*/  
 k = s;  /*开始元素下标*/  
 j = 2*k + 1; /*右子树元素下标*/  
 while (j<n)  
 {  
  if (j<n-1 && *(x+j) < *(x+j+1))/*判断是否满足堆的条件:满足就继续下一轮比较,否则调整。*/  
  {  
   j++;  
  }  
  if (t<*(x+j)) /*调整*/  
  {  
   *(x+k) = *(x+j);  
   k = j; /*调整后,开始元素也随之调整*/  
   j = 2*k + 1;  
  }  
  else /*没有需要调整了,已经是个堆了,退出循环。*/  
  {  
   break;  
  }  
 }  
 *(x+k) = t; /*开始元素放到它正确位置*/  
}  

 功能:堆排序
 输入:数组名称(也就是数组首地址)、数组中元素个数
====================================================

[cpp] view plaincopy
void heap_sort(int *x, int n)  
{  
 int i, k, t;  
 int *p;  
 for (i=n/2-1; i>=0; i--)  
 {  
  sift(x,n,i); /*初始建堆*/  
 }   
 for (k=n-1; k>=1; k--)  
 {  
  t = *(x+0); /*堆顶放到最后*/  
  *(x+0) = *(x+k);  
  *(x+k) = t;  
  sift(x,k,0); /*剩下的数再建堆*/   
 }  
}  
void main()  
{   
 #define MAX 4  
 int *p, i, a[MAX];  
 /*录入测试数据*/  
 p = a;  
 printf("Input %d number for sorting :\n",MAX);  
 for (i=0; i<MAX; i++)  
 {  
  scanf("%d",p++);  
 }  
 printf("\n");  
 /*测试选择排序*/  
 p = a;  
 select_sort(p,MAX);  
 /**/  
 /*测试直接插入排序*/  
 p = a;  
 insert_sort(p,MAX);  
 /*测试冒泡排序*/  
 p = a;  
 insert_sort(p,MAX);  
 /*测试快速排序*/  
 p = a;  
 quick_sort(p,0,MAX-1);  
 /*测试堆排序*/  
 p = a;  
 heap_sort(p,MAX);  
 for (p=a, i=0; i<MAX; i++)  
 {  
  printf("%d ",*p++);  
 }  

 printf("\n");  
 system("pause");  
}  

 

 

 

 

归并排序
介绍:
  归并排序(Merge sort,台湾译作:合并排序)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用
步骤:
申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
设定两个指针,最初位置分别为两个已经排序序列的起始位置
比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
重复步骤3直到某一指针达到序列尾
将另一序列剩下的所有元素直接复制到合并序列尾
排序效果:

图片 7

名称

 复杂度

 说明

 备注

 冒泡排序
Bubble Sort

O(N*N)

 

将待排序的要素看作是竖着排列的“气泡”,较小的成分相比较轻,从而要往上浮

 

 

插入排序

Insertion sort

 

O(N*N)

 

依次取出成分,在曾经排序的要素连串中从后迈入扫描,放到适当的职位

 

起初,已经排序的要素类别为空

 

挑选排序

 

O(N*N)

 

先是在未排序体系中找到最小成分,存放到排序系列的原初地点,然后,再从剩余未排序成分中持续查找最小元素,然后放到排序系列末尾。以此递归。

 

 

火速排序

Quick Sort

 

O(n *log2(n))

 

先采取中间值,然后把比它小的位于左边,大的位于右侧(具体的兑现是从两边找,找到一对后交换)。然后对两边分别接纳那一个历程(递归)。

 

 

堆排序Heap Sort

 

O(n *log2(n))

 

使用堆(heaps)这种数据结构来布局的壹种排序算法。堆是2个接近完全2叉树结构,并同时满足堆属性:即子节点的键值或索引总是小于(或许高于)它的父节点。

类似完全贰叉树

 

Hill排序

SHELL

 

O(n1+£)

0<£<1

 

挑选三个宽度(Step)
,然后按间隔为宽度的单元实行排序.递归,步长逐步变小,直至为壹.

 

 

箱排序
Bin Sort

 

O(n)

 

设置若干个箱子,把关键字等于 k 的记录全都装入到第 k个箱子里 ( 分配 ) ,然后按序号依次将各非空的箱子首尾连接起来 (收集 )。

 

分配排序的一种:通过 ” 分配 ” 和 “收集 “进度来贯彻排序。

 

桶排序

Bucket Sort

 

O(n)

 

桶排序的思辨是把 [0 , 一) 划分为 n个分寸相同的子区间,每一子区间是二个桶。

 

日子复杂度: O(n^2)

手续如下:

  1. 从第1个因素开始,该因素得以认为曾经被排序
  2. 取出下三个因素,在已经排序的要素种类中从后迈入扫描
  3. 假诺该因素(已排序)大于新因素,将该因素移到下1岗位
  4. 再也步骤三,直到找到已排序的成分小于恐怕等于新因素的岗位五.
    将新成分插入到该任务中
  5. 重新步骤二

示例

#pragma mark -- 插入排序---
- (NSMutableArray *)insertSort:(NSMutableArray *)fromArray {

for (int i = 1; i < fromArray.count; i ++)
{
    for (int j = i ; j > 0; j --)
    {
        if ([fromArray[j] integerValue] < [fromArray[j - 1] integerValue])
        {
            NSNumber *temp = fromArray[j];
            fromArray[j] = fromArray[j - 1];
            fromArray[j - 1] = temp;

        }
        else
        {
            break;
        }
    }
}

return fromArray;

}

算法2:选择排序

挑选排序.png

选用排序(Selection
sort)是一种简单直观的排序算法。它的工作规律如下。首先在未排序系列中找到最小成分,存放到排序体系的开局地点,然后,再从剩余未排序成分中继续寻找最小成分,然后放到排序系列末尾。以此类推,直到全体因素均排序实现。

时刻复杂度: O(n^2)

手续如下:

  • 遍历数组,找到最小的因素,将其放置数组开端地点。
  • 从上次小小成分存放的后一个因素起先遍历至数组尾,将小小的要素置于开头处。
  • 再一次上述进程,直到成分排序完结。

示例

#pragma mark ---选择排序---
- (NSMutableArray *)selectSort:(NSMutableArray *)fromArray {
  for (int i = 0; i < fromArray.count - 1; i ++)
  {
      for (int j = i + 1; j < fromArray.count; j++)
      {
          if ([fromArray[i] integerValue] > [fromArray[j] integerValue])
          {
              NSNumber *temp = fromArray[i];
              fromArray[i] = fromArray[j];
              fromArray[j] = temp;

          }
      }
  }
  return fromArray;
}

算法3:冒泡排序

冒泡排序.jpg

冒泡排序(Bubble
Sort)是一种简易的排序算法。它再也地访问过要排序的数列,贰遍相比多个要素,即使她们的次第错误就把她们交流过来。走访数列的行事是双重地拓展直到没有再要求沟通,相当于说该数列已经排序完结。这么些算法的名字由来是因为越小的成分会路过交流稳步“浮”到数列的上面。

光阴复杂度: O(n^2)

步骤如下:

  • 正如相邻的要素。假设首个比第叁个大,就沟通他们四个,直到把最大的因素放到数组尾部。
  • 遍历长度减1,对剩余的因素从头重复以上的步子。
  • 直到未有其余壹对数字需求相比较时成功。

示例

#pragma mark -- 冒泡排序----
- (NSMutableArray *)bubbleSort:(NSMutableArray *)fromArray {
  for (int i = 0; i < fromArray.count; i++)
  {
      for (int j = 0; j < fromArray.count - 1 - i ; j++)
      {
          if ([fromArray[j + 1] integerValue] < [fromArray[j] integerValue])
          {
              NSNumber *temp = fromArray[j + 1];
              fromArray[j + 1] = fromArray[j];
              fromArray[j] = temp;
          }
      }
  }

  return fromArray;
}

算法四:希尔排序

希尔排序.png

希尔排序(Shell
Sort)是插入排序的一种。也称缩短增量排序,是直接插入排序算法的壹种更急速的寻行数墨版本。Hill排序是非稳定排序算法。

光阴复杂度: O(n^1.5)

手续如下:

  • 希尔排序是把记录按下标的任天由命增量分组,对每组使用直接插入排序算法排序;
  • 随着增量慢慢减小,每组包涵的机要词更加多,当增量减至一时,整个文件恰被分成一组,算法便甘休。

示例

#pragma mark --- 希尔排序---

- (NSMutableArray *)shellSort:(NSMutableArray *)fromArray {

    NSInteger incre = fromArray.count/2; //增量

    while (incre > 0)
    {
        for (int i = 0; i < incre; i ++)   //根据增量分为若干子序列
        {
            for (int j = i ; j < fromArray.count; j += incre)  //分组内插入排序
            {
                for (int k = j ; k > i; k -= incre)
                {
                    if ([fromArray[k] integerValue] < [fromArray[k - incre] integerValue])
                    {
                        NSNumber *temp = fromArray[k];
                        fromArray[k] = fromArray[k - incre];
                        fromArray[k - incre] = temp;
                    }
                    else
                    {
                        break;
                    }
                }
             }
        }

        incre /= 2;
    }

    return fromArray;
}

算法伍:急迅排序

飞速排序.gif

急忙排序(Quicksort)是对冒泡排序的壹种创新。它的着力思想是:通过壹趟排序将要排序的多少分割成单身的两片段,当中壹些的有着数据都比其余一些的装有数据都要小,然后再按此情势对那两有些数据分别举办快捷排序,整个排序进程能够递归进行,以此达到整个数据变成有序种类。

时光复杂度:O(N*logN)

步骤:

  • 从数列中挑出3个要素,称为 “基准”(pivot),
  • 再也排序数列,全体因素比基准值小的摆放在基准后面,全数因素比基准值大的摆在基准的前边(相同的数能够到任一边)。在那个分区退出之后,该规范就处于数列的中游地点。那个名称为分区(partition)操作。
  • 递归地(recursive)把小于基准值成分的子数列和超越基准值成分的子数列排序。

示例

#pragma mark ----- 快速排序 --- 

- (NSMutableArray *)quickSork:(NSMutableArray *)fromArray {

    NSMutableArray *leftArray = [NSMutableArray array];
    NSMutableArray *rightArray = [NSMutableArray array];
    if (fromArray.count < 1)
    {
        return fromArray;
    }

    //随机一个基点
    int randomPivotPoint = arc4random() % fromArray.count;
    NSNumber *pivotValue = fromArray[randomPivotPoint];

    [fromArray removeObject:pivotValue];

    for (NSNumber *num in fromArray)
    {
        if ([num integerValue] < [pivotValue integerValue])
        {
            [leftArray addObject:num];
        }
        else
        {
            [rightArray addObject:num];
        }
    }

    //递归
    NSMutableArray *sortArray = [NSMutableArray array];
    [sortArray addObjectsFromArray:[self quickSork:leftArray]];
    [sortArray addObject:pivotValue];
    [sortArray addObjectsFromArray:[self quickSork:rightArray]];


    return sortArray;
}

算法6:归并排序

归并算法.png

归并排序(Merge
sort)是手无寸铁在联合操作上的一种有效的排序算法。该算法是采取分治法(Divide
and Conquer)的一个不行典型的采取。

光阴复杂度:O(N*logN)

手续如下:

  • 报名空间,创造七个数组,长度分别为三个有序数组的长短
  • 设定多少个指针,最初地方分别为四个曾经排序系列的序曲地方
  • 比较七个指针所指向的因素,选取相对小的要素放入到统1空间,并活动指针到下一任务
  • 再一次步骤三直到某一指南针达到连串尾
  • 将另一类别剩下的享有因素直接复制到合并系列尾

示例

#pragma mark --- 归并排序 ------

- (void)mergeSort:(NSMutableArray *)list startIndex:(NSInteger)startIndex endIndex:(NSInteger)endIndex{

    if (startIndex < endIndex)
    {

        //取中间位置,将左右两边分别递归进行归并,直至左右两边只剩1个元素
        NSInteger middle = (startIndex + endIndex) / 2;
        [self mergeSort:list startIndex:startIndex endIndex:middle];
        [self mergeSort:list startIndex:middle+1 endIndex:endIndex];

        //对左右2边的数据进行合并
        NSInteger i = startIndex; //左边数据的起始位置
        NSInteger j = middle+1; //右边数据的起始位置

        NSMutableArray *temp = [NSMutableArray array]; //临时数组
        while (i <= middle && j <= endIndex)
        {
            //如果左边数据较小,则将其放到临时数组里,并将左边位置向后移一位
            if ([list[i] integerValue] < [list[j] integerValue])
            {
                [temp addObject:list[i]];
                i++;
            }
            //否则将右边数据放到临时数组里,并将右边位置向后移一位
            else
            {
                [temp addObject:list[j]];
                j++;
            }
        }
        //如果左边还有数据,则将剩余的部分全都复制到临时数组里
        while (i <= middle)
        {
            [temp addObject:list[i]];
            i++;
        }
        //如果右边还有数据(左右两边只可能存在一边有剩余数据的情况),则将剩余的部分全都复制到临时数组里
        while (j <= endIndex)
        {
            [temp addObject:list[j]];
            j++;
        }

        //再将临时数组里的数据(已经排好序了)保存到原始数据中,以达到对原始数据的排序
        for (i=0; i < temp.count; i++)
        {
            //注意:需要从startIndex位置开始,因为这里是递归调用的
            [list replaceObjectAtIndex:startIndex withObject:temp[i]];
            startIndex++;
        }
    }
}

算法七:堆排序

堆排序.png

堆排序(Heap
Sort)是指使用堆那种数据结构所设计的一种排序算法。堆是二个类似完全二叉树的协会,并同时满足堆性质:即子结点的键值或索引总是小于(可能当先)它的父节点。

日子复杂度:O(N*logN) 由于每一趟重复上升堆的时日复杂度为O(logN),共N

  • 三遍重复上升堆操作,再增进前面建立堆时N /
    三回向下调整,每便调整时间复杂度也为O(logN)。壹次操作时间相加照旧O(N *
    logN)。

步骤如下:

  • 将数据开端化成堆,即将数据存款和储蓄到多少个一心贰叉树中,再协会大顶堆(升序)或小顶堆(降序)。
  • 换来堆顶元素和末段一个因素,获得3个新的堆,被换来到底层的香艳部分为平稳,别的堆为严节且可能不满意堆特性,所以要求对别的部分实行堆调整,调整好后继续将堆顶成分和终极几个堆低未排序成分举办交换……

示例

#pragma mark ---- 堆排序 -------
/**
 *    array: 数据源
 *    index: 节点索引
 */
-(void)maxHeapAdjust:(NSMutableArray *)array index:(NSInteger)index  length:(NSInteger)length
{
    NSInteger leftChildIndex = index * 2 + 1;  //获取该节点的左子节点索引
    NSInteger rightChildIndex = index * 2 + 2; //获取该节点的右子节点索引
    NSInteger maxValueIndex = index;//暂时把该索引当做最大值所对应的索引

    //判断左子节点的值是否大于当前最大值
    if (leftChildIndex < length && [array[leftChildIndex] integerValue] > [array[maxValueIndex] integerValue])
    {
        //把左子节点的索引作为最大值所对应的索引
        maxValueIndex = leftChildIndex;
    }


    //判断右子节点的值是否大于当前最大值
    if (rightChildIndex < length && [array[rightChildIndex] integerValue] > [array[maxValueIndex] integerValue])
    {
        maxValueIndex = rightChildIndex;
    }

    //如果该节点不是最大值所在的节点 则将其和最大值节点进行交换
    if (maxValueIndex != index)
    {
        [array exchangeObjectAtIndex:maxValueIndex withObjectAtIndex:index];

    }

}

//构建最大栈
- (void)createMaxHeap:(NSMutableArray*)array
{

    /*
     从最后一个非叶子节点开始 自下而上进行调整堆
     */
    for (NSInteger i = (array.count/2 - 1);i >= 0; --i)
    {
        [self maxHeapAdjust:array index:i length:array.count] ;
    }

    //从最后一个元素开始对序列进行调整,不断的缩小调整的范围直到第一个元素
    for(int j = array.count - 1;j > 0; --j)
    {
        //把第一个元素和当前的最后一个元素交换,
        [array exchangeObjectAtIndex:0 withObjectAtIndex:j];
        //不断缩小调整heap的范围,每一次调整完毕保证第一个元素是当前序列的最大值
        [self maxHeapAdjust:array index:0 length:j];
    }

}

//最大栈排序
- (void)maxHeapSort:(NSMutableArray *)fromArray
{

    [self createMaxHeap:fromArray];
}

———次之局部:链表————-

判定四个链表是还是不是有环

宣示二个节点
typedef int ElemType;  // 假定数据类型为int
typedef struct Node{

    ElemType data;
    struct Node *next;

} Node,*LinkList;
代码实现
#pragma mark  ------------链表----------------

#pragma mark ------ 判断一个链表是否有环 -----
//如何判断是否有环?如果有两个头结点指针,一个走的快,一个走的慢,那么若干步以后,快的指针总会超过慢的指针一圈。
- (BOOL)hasLoop:(LinkList)pHead{
    LinkList fast,slow;
    fast = pHead;
    slow = pHead;
    //如果无环,则fast先走到终点
    //当链表长度为奇数时,fast->Next为空
    //当链表长度为偶数时,fast为空

    while (fast != NULL && fast -> next != NULL)
    {
        fast = fast -> next -> next;
        slow = slow -> next;

         //如果有环,则fast会超过slow一圈
        if (fast == slow)
        {
            break;
        }
    }

    if (fast == NULL || fast -> next == NULL)
    {
        return NO;
    }
    else
        return YES;


}

Every day to write, to be continued…

相关文章