数据结构是程序设计的重要基础，它所讨论的内容和技术对从事软件项目的开发有重要作用。学习数据结构要达到的目标是学会从问题出发，分析和研究计算机加工的数据的特性，以便为应用所涉及的数据选择适当的逻辑结构、存储结构及其相应的操作方法，为提高利用计算机解决问题的效率服务。
假设含 n个记录的文件内容为｛R
1,R
2,…,R
n}，相应的关键字为{k
1,k
2,…,k
n}。经过排序确定一种排列{R
j1,R
j2,…,R
jn}，使得它们的关键字满足以下递增（或递减）关系：k
j1≤k
j2≤…≤k
jn（或k
j1≥k
j2≥…≥k
jn)。
若在待排序的一个序列中，R
i 和 R
j 的关键字相同，即k
i=k
j，且在排序前 R
i 领先于R
j，那么在排序后，如果R
i 和R
j 的相对次序保持不变，R
i 仍领先于R
j，则称此类排序方法为稳定的。若在排序后的序列中有可能出现R
j 领先于R
i 的情形，则称此类排序为不稳定的。
(1）内部排序。内部排序指待排序记录全部存放在内存中进行排序的过程。
(2）外部排序。外部排序指待排序记录的数量很大，以至于内存不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。
在排序过程中需要进行下列两种基本操作：比较两个关键字的大小；将记录从一个位置移动到另一个位置。前一种操作对大多数排序方法来说都是必要的，后一种操作可以通过改变记录的存储方式来避免。
1、直接插入排序
直接插入排序是一种简单的排序方法，具体做法是：在插入第 i 个记录时，R1、R2、…、Ri-1 已经排好序，这时将 Ri 的关键字 ki 依次与关键字 ki-1、ki-2 等进行比较，从而找到应该插入的位置并将 Ri 插入，插入位置及其后的记录依次向后移动。
【算法】直接插入排序算法。
void Insertsort(int data[],int n)
/*将数组data[0]~data[n-1］中的n个整数按非递减有序的方式进行排列*/
{
inti,j;
int tmp;
for(i=1; i<n; i++){
if(data[i] <data[i-1]){
tmp=data[i]; data[i]=data[i-1];
for(j=i-1; j>=0&&data[j]>tmp; j--) data[j+1]=data[j];
data[j+1]=tmp;
}/*if*/
}/*for*/
}/*Insertsort*/
直接插入排序法在最好情况下（待排序列已按关键码有序），每趟排序只需作 1 次比较目不需要移动元素，因此 n 个元素排序时的总比较次数为 n-1 次，总移动次数为 0 次。在最坏情况下（元素已经逆序排列），进行第 i 趟排序时，待插入的记录需要同前面的 i 个记录都进行 1 次比较，因此，总比较次数为
Σ
i
=
1
n
−
1
i
=
n
(
n
−
1
)
2
{huge Sigma}_{i=1}^{n-1}i=frac{n(n-1)}2
Σi=1n−1i=2n(n−1)。排序过程中，第 i 趟排序时移动记录的次数为 i+1（包括移进、移出tmp)，总移动次数为
Σ
i
=
2
n
(
i
+
1
)
=
(
n
+
3
)
(
n
−
2
)
2
{huge Sigma}_{i=2}^{n}(i+1)=frac{(n+3)(n-2)}2
Σi=2n(i+1)=2(n+3)(n−2)。
直接插入排序是一种稳定的排序方法，其时间复杂度为O(n2)。在排序过程中仅需要一个元素的辅助空间，空间复杂度为O(1)。
2、冒泡排序
n个记录进行冒泡排序的方法是：首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则交换这两个记录的值，然后比较第二个记录和第三个记录的关键字，依此类推，直到第n-1个记录和第n个记录的关键字比较过为止。上述过程称为第一趟冒泡排序，其结果是关键字最大的记录被交换到第n个记录的位置上。然后进行第二趟冒泡排序，对前n-1 个记录进行同样的操作，其结果是关键字次大的记录被交换到第 n-1个记录的位置上。最多进行n-1 趟，所有记录有序排列。若在某趟冒泡排序过程没有进行相邻位置的元素交换处理，则可结束排序过程。
冒泡排序法在最好情况下（待排序列已按关键码有序），只需做 1 趟排序，元素的比较次数为 n-1 且不需要交换元素，因此总比较次数为 n-1 次，总交换次数为 0次。在最坏情况下（元素已经逆序排列），进行第 j 趟排序时，最大的 j-1 个元素已经排好序，其余的 n-(j-1) 个元素需要进行 n-j 次比较和 n-j 次交换，因此总比较次数为
Σ
j
=
1
n
−
1
(
n
−
j
)
=
n
(
n
−
1
)
2
{huge Sigma}_{j=1}^{n-1}(n-j)=frac{n(n-1)}2
Σj=1n−1(n−j)=2n(n−1)，总交换次数为
Σ
j
=
1
n
−
1
(
n
−
j
)
=
n
(
n
−
1
)
2
{huge Sigma}_{j=1}^{n-1}(n-j)=frac{n(n-1)}2
Σj=1n−1(n−j)=2n(n−1)。
冒泡排序是一种稳定的排序方法，其时间复杂度为O(n2)。在排序过程中仅需要一个元素的辅助空间用于元素的交换，空间复杂度为O(1)。
3、简单选择排序
n个记录进行简单选择排序的基本方法是：通过 n-i(1≤i≤n）在次关键字之间的比较，从n-i+1 个记录中选出关键字最小的记录，并和第 i 个记录进行交换，当 i 等于 n 时所有记录有序排列。
【算法】简单选择排序算法。
void SelectSort(int data[], int n)
/*将数组data中的n个整数按非递减有序的方式进行排列*/
{
int i,j, k,tmp;
for(i=0; i<n-1; i++){
k=i;
for(j=i+1; j<n; j++) /*找出最小关键字的下标*/
if(data[j]<data[k]) k=j;
if(k!=i){
tmp=data[i]; data[i]=data[k]; data[k]=tmp;
}/*if*/
}/*for*/
}/*SelectSort*/
简单选择排序法在最好情况下（待排序列已按关键码有序），不需要移动元素，因此 n个元素排序时的总移动次数为0次。在最坏情况下（元素已经逆序排列），前
n
2
frac n2
2n趟中，每趟排序移动记录的次数都为3次（两个数组元素交换值），其后不再移动元素，共进行n-1趟排序，总移动次数为3(n-1)/2。无论在哪种情况下，元素的总比较次数为
Σ
i
=
1
n
−
1
(
n
−
i
)
=
n
(
n
−
1
)
2
{huge Sigma}_{i =1}^{n-1}(n-i)=frac{n(n-1)}2
Σi=1n−1(n−i)=2n(n−1)。
简单选择排序是一种不稳定的排序方法，其时间复杂度为 O(n2)。在排序过程中仅需要一个元素的辅助空间用于数组元素值的交换，空间复杂度为O(1)。
原文地址:https://blog.csdn.net/qq_33501207/article/details/136007205
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.7code.cn/show_65807.html
如若内容造成侵权/违法违规/事实不符，请联系代码007邮箱：suwngjj01@126.com进行投诉反馈，一经查实，立即删除！
