数据结构之简单排序

  数据结构是程序设计的重要基础，它所讨论的内容和技术对从事软件项目的开发有重要作用。学习数据结构要达到的目标是学会从问题出发，分析和研究计算机加工的数据的特性，以便为应用所涉及的数据选择适当的逻辑结构、存储结构及其相应的操作方法，为提高利用计算机解决问题的效率服务。

  假设含 n个记录的文件内容为｛R
₁,R
₂,…,R
_n}，相应的关键字为{k
₁,k
₂,…,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 个记录时，R₁、R₂、…、R_i-1 已经排好序，这时将 R_i 的关键字 k_i 依次与关键字 k_i-1、k_i-2 等进行比较，从而找到应该插入的位置并将 R_i 插入，插入位置及其后的记录依次向后移动。
  【算法】直接插入排序算法。

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−1​i=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(n²)。在排序过程中仅需要一个元素的辅助空间，空间复杂度为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(n²)。在排序过程中仅需要一个元素的辅助空间用于元素的交换，空间复杂度为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(n²)。在排序过程中仅需要一个元素的辅助空间用于数组元素值的交换，空间复杂度为O(1)。

代码007普通

打赏 收藏 海报 链接