各种算法排序思想小结

时间：2024.4.8

1.选择排序

基本思想：

每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。

2.直接插入排序

基本思想：

每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。

3.冒泡排序

基本思想：

依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。由于在排序过程中总是小数往前放，大数往后放，相当于气泡往上升，所以称作冒泡排序。

4.Shell排序

基本思想：

先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。

5.堆排序

基本思想：

① 先将初始文件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]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和

有序区R[n- 1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。 …… 直到无序区只有一个元素为止。

6.快速排序

基本思想：

快速排序（Quicksort）是对冒泡排序的一种改进。

它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

7.归并排序

基本思想：

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

归并操作的工作原理如下：

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

设定两个指针，最初位置分别为两个已经排序序列的起始位置

比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置重复步骤3直到某一指针达到序列尾

将另一序列剩下的所有元素直接复制到合并序列尾

8.基数排序

基本思想：

基数排序法又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的比较性排序法。

最高位优先(Most Significant Digit first)法，简称MSD法：先按k1排序分组，同一组中记录，关键码k1相等，再对各组按k2排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码kd对各子组排序后。再将各组连接起来，便得到一个有序序列。

最低位优先(Least Significant Digit first)法，简称LSD法：先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。

第二篇：各种排序算法思想小结

1.选择排序

基本思想：

每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。

2.直接插入排序

基本思想：

每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。

3.冒泡排序

基本思想：

依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。　　由于在排序过程中总是小数往前放，大数往后放，相当于气泡往上升，所以称作冒泡排序。

4.Shell排序

基本思想：

先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。　　

该方法实质上是一种分组插入方法。

5.堆排序

基本思想：

① 先将初始文件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]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n- 1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。　　…… 　　

直到无序区只有一个元素为止。

6.快速排序

基本思想：

快速排序（Quicksort）是对冒泡排序的一种改进。

7.归并排序

基本思想：

归并操作的工作原理如下：

　　申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

　　设定两个指针，最初位置分别为两个已经排序序列的起始位置

　　比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

　　重复步骤3直到某一指针达到序列尾

　　将另一序列剩下的所有元素直接复制到合并序列尾

8.基数排序

基本思想：

最低位优先(Least Significant Digit first)法，简称LSD法：先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。

第三篇：用php实现的各种排序算法总结

用php实现的各种排序算法总结

优化php性能的五个实用技巧：

以下是五个优化技巧，熟练掌握后对于开发还是很有帮助的。

1. 对字符串使用单引号

PHP 引擎允许使用单引号和双引号来封装字符串变量，但是这个是有很大的差别的！使用双引号的字符串告诉 PHP 引擎首先去读取字符串内容，查找其中的变量，并改为变量对应的值。一般来说字符串是没有变量的，所以使用双引号会导致性能不佳。最好是使用字符串连接而不是双引号字符串。

BAD:

$output = “This is a plain string”;

GOOD:

$output = 'This is a plain string';

BAD:

$type = “mixed”;

$output = “This is a $type string”;

GOOD:

$type = 'mixed';

$output = 'This is a ' . $type .' string';

2. 不要随便就复制变量

有时候为了使 PHP 代码更加整洁，一些 PHP 新手（包括我）会把预定义好的变量复制到一个名字更简短的变量中，其实这样做的结果是增加了一倍的内存消耗，只会使程序更加慢。试想一下，在下面的例子中，如果用户恶意插入 512KB 字节的文字到文本输入框中，这样就会导致 1MB 的内存被消耗！

BAD:

$description = $_POST['description'];

echo $description;

GOOD:

echo $_POST['description'];

3. 使用 echo 函数来输出字符串

使用 echo（）函数来打印结果出了有更容易阅读之外，在下个例子中，你还可以看到有更好的性能。

BAD:

print（$myVariable）；

GOOD:

echo $myVariable;

4. 不要在 echo 中使用连接符

很***PHP 程序员（有包括我）不知道在用恶臭输出多个变量的时候，其实可以使用逗号来分开的，而不必用字符串先把他们先连起来，如下面的第一个例子中，由于使用了连接符就会有性能问题，因为这样就会需要 PHP 引擎首先把所有的变量连接起来，然后在输出，而在第二个例子中，PHP 引擎就会按照循序输出他们。

BAD:

echo 'Hello, my name is' . $firstName . $lastName . ' and I live in ' . $city;

GOOD:

echo 'Hello, my name is' , $firstName , $lastName , ' and I live in ' , $city;

5. 使用 switch/case 代替 if/else

对于只有单个变量的判断，使用 switch/case 语句而不是 if/else 语句，会有更好的性能，并且代码更加容易阅读和维护。

BAD:

if（$_POST['action'] == 'add‘） {

addUser（）；

} elseif （$_POST['action'] == 'delete’） {

deleteUser（）；

} elseif （$_POST['action'] == 'edit‘） {

editUser（）；

} else {

defaultAction（）；

}

GOOD:

switch（$_POST['action']） {

case 'add':

addUser（）；

break;

case 'delete':

用php实现的各种排序算法，冒泡排序，交换排序，选择法排序，插入法排序，快速排序，根据实际情况可选则不同的排序算法。效率也有所不同。

冒泡排序：<?php

function BubbleSort（$arr）{

$num = count（$arr）；

for（$i=1;$i<$num;$i++）{

for（$j=$num-1;$j>=$i;$j--）{

if（$arr[$j]<$arr[$j-1]）{

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

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

$arr[$j] = $iTemp;

}

return $arr;

}

交换法排序：<?php

function ExchangeSort（$arr）{

$num = count（$arr）；

for（$i=0;$i<$num-1;$i++）{

for（$j=$i+1;$j<$num;$j++）{

if（$arr[$j]<$arr[$i]）{

$iTemp = $arr[$i];

$arr[$i] = $arr[$j];

$arr[$j] = $iTemp;

}

return $arr;

}

选择法排序：<?php

function SelectSort（$arr）{

$num = count（$arr）；

for（$i=0;$i<$num-1;$i++）{

$iTemp = $arr[$i];

$iPos = $i;

for（$j=$i+1;$j<$num;$j++）{

if（$arr[$j]<$iTemp）{

$iTemp = $arr[$j];

$iPos = $j;

}

$arr[$iPos] = $arr[$i];

$arr[$i] = $iTemp;

}

return $arr;

}

插入法排序：<?php

function InsertSort（$arr）{

$num = count（$arr）；

for（$i=1;$i<$num;$i++）{

$iTemp = $arr[$i];

$iPos = $i-1;

while（（$iPos>=0） && （$iTemp<$arr[$iPos]））{ $arr[$iPos+1] = $arr[$iPos];

$iPos--;

}

$arr[$iPos+1] = $iTemp;

}

return $arr;

}

快速排序 :<?php

function QuickSort（$arr）{ $num = count（$arr）； $l=$r=0;

for（$i=1;$i<$num;$i++）{ if（$arr[$i] < $arr[0]）{ $left[] = $arr[$i];

$l++;

}else{

$right[] = $arr[$i];

$r++;

}

if（$l > 1）{

$left = QuickSort（$left）； }

$new_arr = $left;

$new_arr[] = $arr[0]; if（$r > 1）{

$right = QuickSort（$right）； }

for（$i=0;$i<$r;$i++）{ $new_arr[] = $right[$i]; }

return $new_arr;

}

$arr = array（7,1,6,5,2）；

$arr_new = QuickSort（$arr）； ?>

deleteUser（）；

break;

case 'edit':

editUser（）；

break;

default:

更多相关推荐：

用php实现的各种排序算法总结: 用php实现的各种排序算法总结优化php性能的五个实用技巧：以下是五个优化技巧，熟练掌握后对于开发还是很有帮助的。1.对字符串使用单引号PHP引擎允许使用单引号和双引号来封装字符串变量，但是这个是有很大的差别的…
各种排序算法的总结和比较: 1快速排序（QuickSort）快速排序是一个就地排序，分而治之，大规模递归的算法。从本质上来说，它是归并排序的就地版本。快速排序可以由下面四步组成。（1）如果不多于1个数据，直接返回。（2）一般选择序列最左边…
Java各种排序算法总结: 排序是程序开发中一种非常常见的操作对一组任意的数据元素或记录经过排序操作后就可以把他们变成一组按关键字排序的有序队列对一个排序算法来说一般从下面3个方面来衡量算法的优劣1时间复杂度它主要是分析关键字的比较次数和...
最常用的排序算法总结: 实际应用中最常用的排序是快速排序和堆排序所谓堆排序就是将最小的一个值放到堆栈的顶部这样就可以使最后出来的数完成排序快速排序是不稳定的堆排序是稳定的所谓稳定就是当两个值相等时排序后两个值的顺序和排序前相同以上两种...
各种排序算法总结: 1冒泡排序交换排序方法之一冒小泡voidBublesortintaintn定义两个参数数组首地址与数组大小intijtempfori0iltn1iforji1jltnj注意循环的上下限ifaigtajtempa...
各种排序算法小结: 各种排序算法小结排序算法是一种基本并且常用的算法由于实际工作中处理的数量巨大所以排序算法对算法本身的速度要求很高而一般我们所谓的算法的性能主要是指算法的复杂度一般用O方法来表示在后面我将给出详细的说明对于排序的...
经典排序算法总结(代码): 经典排序算法总结代码fly分享目录冒泡法2快速排序3插入排序4希尔shell排序5选择排序6堆排序7归并排序9附排序算法原理flash演示includeltiostreamgtincludeltstringgt...

各种排序算法的稳定性和时间复杂度小结: 选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法，冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。冒泡法：这是最原始，也是众所周知的最慢的算法了。他的名字的由来因为它的工作看来象是冒泡：复杂度为O…
排序算法总结: 现有序列{9,3,5,1,6,2,8,4,7}，以此为例子，阐述各个常用排序算法。直接插入排序：每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。第一趟比较前两个数,然后把第二个数按大…
排序算法总结: 按平均时间将排序分为四类：（1）平方阶(O(n2))排序一般称为简单排序，例如直接插入、直接选择和冒泡排序；（2）线性对数阶(O(nlgn))排序如快速、堆和归并排序；（3）O(n1+￡)阶排序￡是介于0和1之…
c语言排序算法总结(主要是代码实现): 冒泡排序（BubbleSort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。…
八大排序算法总结: 八大排序算法总结插入排序1.直接插入排序原理：将数组分为无序区和有序区两个区，然后不断将无序区的第一个元素按大小顺序插入到有序区中去，最终将所有无序区元素都移动到有序区完成排序。要点：设立哨兵，作为临时存储和判…

热门关注