基本排序算法原理与代码

排序算法是最基本最常用的算法,不同的排序算法在不同的场景或应用中会有不同的表现,我们需要对各种排序算法熟练才能将它们应用到实际当中,才能更好地发挥它们的优势。今天,来总结下各种排序算法。


下面这个表格总结了各种排序算法的复杂度与稳定性:


各种排序算法复杂度比较.png

冒泡排序

冒泡排序可谓是最经典的排序算法了,它是基于比较的排序算法,时间复杂度为O(n^2),其优点是实现简单,n较小时性能较好。

算法原理

相邻的数据进行两两比较,小数放在前面,大数放在后面,这样一趟下来,最小的数就被排在了第一位,第二趟也是如此,如此类推,直到所有的数据排序完成

c++代码实现

void bubble_sort(int arr[], int len)

{

     for (int i = 0; i < len - 1; i++)

     {

         for (int j = len - 1; j > i; j--)

         {

             if (arr[j] < arr[j - 1])

             {

                 int temp = arr[j];

                 arr[j] = arr[j - 1];

                 arr[j - 1] = temp;

             }

         }

     }

}

选择排序

算法原理

先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

c++代码实现

 void select_sort(int arr[], int len)

 {

     for (int i = 0; i < len; i++)

     {

         int index = i;

         for (int j = i + 1; j < len; j++)

         {

             if (arr[j] < arr[index])

                 index = j;

         }

         if (index != i)

         {

             int temp = arr[i];

             arr[i] = arr[index];

             arr[index] = temp;

}

}

}

插入排序

算法原理

将数据分为两部分,有序部分与无序部分,一开始有序部分包含第1个元素,依次将无序的元素插入到有序部分,直到所有元素有序。插入排序又分为直接插入排序、二分插入排序、链表插入等,这里只讨论直接插入排序。它是稳定的排序算法,时间复杂度为O(n^2)

c++代码实现

 void insert_sort(int arr[], int len)

 {

     for (int i = 1; i < len; i ++)

     {

         int j = i - 1;

         int k = arr[i];

         while (j > -1 && k < arr[j] )

         {

             arr[j + 1] = arr[j];

             j --;

         }

         arr[j + 1] = k;

     }

 }

快速排序

算法原理

快速排序是目前在实践中非常高效的一种排序算法,它不是稳定的排序算法,平均时间复杂度为O(nlogn),最差情况下复杂度为O(n^2)。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

c++代码实现

void quick_sort(int arr[], int left, int right)

{

 if (left < right)

 {

     int i = left, j = right, target = arr[left];

     while (i < j)

     {

         while (i < j && arr[j] > target)

             j--;

         if (i < j)

             arr[i++] = arr[j];

         while (i < j && arr[i] < target)

             i++;

         if (i < j)

             arr[j] = arr[i];

     }

     arr[i] = target;

     quick_sort(arr, left, i - 1);

     quick_sort(arr, i + 1, right);

 }

}

归并排序

算法原理

归并排序具体工作原理如下(假设序列共有n个元素):

将序列每相邻两个数字进行归并操作(merge),形成floor(n/2)个序列,排序后每个序列包含两个元素

将上述序列再次归并,形成floor(n/4)个序列,每个序列包含四个元素

重复步骤2,直到所有元素排序完毕

归并排序是稳定的排序算法,其时间复杂度为O(nlogn),如果是使用链表的实现的话,空间复杂度可以达到O(1),但如果是使用数组来存储数据的话,在归并的过程中,需要临时空间来存储归并好的数据,所以空间复杂度为O(n)

c++代码实现

 void merge(int arr[], int temp_arr[], int start_index, int mid_index, int end_index)

 {

     int i = start_index, j = mid_index + 1;

     int k = 0;

     while (i < mid_index + 1 && j < end_index + 1)

     {

         if (arr[i] > arr[j])

             temp_arr[k++] = arr[j++];

         else

             temp_arr[k++] = arr[i++];

     }

     while (i < mid_index + 1)

     {

         temp_arr[k++] = arr[i++];

     }

     while (j < end_index + 1)

         temp_arr[k++] = arr[j++];

     for (i = 0, j = start_index; j < end_index + 1; i ++, j ++)

         arr[j] = temp_arr[i];

 }

 void merge_sort(int arr[], int temp_arr[], int start_index, int end_index)

 {

     if (start_index < end_index)

     {

         int mid_index = (start_index + end_index) / 2;

         merge_sort(arr, temp_arr, start_index, mid_index);

         merge_sort(arr, temp_arr, mid_index + 1, end_index);

         merge(arr, temp_arr, start_index, mid_index, end_index);

     }

 }

堆排序

二叉堆

二叉堆是完全二叉树或者近似完全二叉树,满足两个特性

父结点的键值总是大于或等于(小于或等于)任何一个子节点的键值

每个结点的左子树和右子树都是一个二叉堆

当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆。一般二叉树简称为堆。

堆的存储

一般都是数组来存储堆,i结点的父结点下标就为(i – 1) / 2。它的左右子结点下标分别为2 * i + 1和2 * i + 2。如第0个结点左右子结点下标分别为1和2。存储结构如图所示:

堆结构.png

堆排序原理

堆排序的时间复杂度为O(nlogn)

算法原理(以最大堆为例)

先将初始数据R[1..n]建成一个最大堆,此堆为初始的无序区

再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换,由此得到新的无序区R[1..n-1]和有序区R[n],且满足R[1..n-1].keys≤R[n].key

由于交换后新的根R[1]可能违反堆性质,故应将当前无序区R[1..n-1]调整为堆。

重复2、3步骤,直到无序区只有一个元素为止。

c++代码实现

/**

* 将数组arr构建大根堆

* @param arr 待调整的数组

* @param i   待调整的数组元素的下标

* @param len 数组的长度

*/

void heap_adjust(int arr[], int i, int len)

{

   int child;

   int temp;

   for (; 2 * i + 1 < len; i = child)

   {

       child = 2 * i + 1;  // 子结点的位置 = 2 * 父结点的位置 + 1

       // 得到子结点中键值较大的结点

       if (child < len - 1 && arr[child + 1] > arr[child])

           child ++;

       // 如果较大的子结点大于父结点那么把较大的子结点往上移动,替换它的父结点

       if (arr[i] < arr[child])

       {

           temp = arr[i];

           arr[i] = arr[child];

           arr[child] = temp;

       }

       else

           break;

   }

}

/**

* 堆排序算法

*/

void heap_sort(int arr[], int len)

{

   int i;

   // 调整序列的前半部分元素,调整完之后第一个元素是序列的最大的元素

   for (int i = len / 2 - 1; i >= 0; i--)

   {

       heap_adjust(arr, i, len);

   }

   for (i = len - 1; i > 0; i--)

   {

       // 将第1个元素与当前最后一个元素交换,保证当前的最后一个位置的元素都是现在的这个序列中最大的

       int temp = arr[0];

       arr[0] = arr[i];

       arr[i] = temp;

       // 不断缩小调整heap的范围,每一次调整完毕保证第一个元素是当前序列的最大值

       heap_adjust(arr, 0, i);

   }

}

未完待续

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 206,968评论 6 482
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 88,601评论 2 382
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 153,220评论 0 344
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 55,416评论 1 279
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 64,425评论 5 374
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,144评论 1 285
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,432评论 3 401
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,088评论 0 261
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 43,586评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,028评论 2 325
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,137评论 1 334
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,783评论 4 324
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,343评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,333评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,559评论 1 262
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,595评论 2 355
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,901评论 2 345

推荐阅读更多精彩内容