分别采用直接插入排序,简单选择排序,冒泡排序,快速排序,归并排序的算法对给 定的线性表进行排序。
时间: 2023-06-27 20:07:41 浏览: 96
调整堆示例-各种排序方法的算法
直接插入排序:
直接插入排序的基本思想是将一个记录插入到已排好序的有序表中,从而得到一个新的、记录数增加1的有序表。
具体步骤如下:
1.将第一个元素看作是一个有序的子序列,然后从第二个元素开始,依次将每个元素插入到已经排好序的子序列中。
2.将未排序的第一个元素,即a[1]与a[0]比较大小,如果a[1] < a[0],则将a[1]插入到a[0]前面,否则a[1]已经是有序的了。
3.将未排序的第二个元素,即a[2]与已经排好序的子序列比较大小,找到合适的位置插入,依次类推。
简单选择排序:
简单选择排序的基本思想是在未排序的序列中找到最小元素,然后将其放到已排序序列的末尾。
具体步骤如下:
1.将序列分为已排序和未排序两部分,初始时已排序部分为空,未排序部分包括所有元素。
2.在未排序部分中找到最小的元素,将其放到已排序部分的末尾。
3.重复步骤2,直到未排序部分为空。
冒泡排序:
冒泡排序的基本思想是比较相邻的两个元素,如果前一个元素比后一个元素大,则交换这两个元素的位置,从而使较大的元素逐渐往后移动。
具体步骤如下:
1.从序列的第一个元素开始,依次比较相邻的两个元素,如果前一个元素比后一个元素大,则交换这两个元素的位置。
2.重复步骤1,直到序列中所有相邻的元素都被比较过一次。
3.重复步骤1和步骤2,直到序列中的所有元素都排好序。
快速排序:
快速排序的基本思想是通过一趟排序将待排序序列分割成独立的两部分,其中一部分的所有元素都比另一部分的所有元素小,然后再按照此方法依次对两部分继续进行排序,直到整个序列有序。
具体步骤如下:
1.选取一个基准元素,一般选择第一个元素或者最后一个元素。
2.将序列中所有小于基准元素的元素放在基准元素的左边,所有大于基准元素的元素放在基准元素的右边。
3.对左右两个子序列分别进行快速排序,直到整个序列有序。
归并排序:
归并排序的基本思想是将两个有序的子序列合并成一个有序的序列。
具体步骤如下:
1.将序列分成两个子序列,分别进行归并排序。
2.将两个有序的子序列合并成一个有序的序列。
3.重复步骤1和步骤2,直到序列有序。
阅读全文