数据排序

1 排序的基本概念和分类

排序定义：假设含有n个记录的序列为{r1, r2,…..,rn},其相应的关键字分别为{k1,k2,…….,kn},需确定1,2，…，n的一种排列p1,p2,p3…..,pn,使其相应的关键字满足kp1<=kp2<=kp3<=…<=kpn（非递减或非递增）关系，即使得序列称为一个按关键字有序的序列{rp1,rp2,rp3,…,rpn}，这样的操作就称为排序。

稳定性：假设ki=kj(1<=i<=n,1<=j<=n,i<>j)，且在排序前的序列中ri领先于rj（即i<j）。如果排序后ri仍然领先于rj，则称所有的排序方法是稳定的；反之，若可能使得排序后的序列中rj领先于ri ，则称为所有的排序方法是不稳定的。

2 内排序和外排序

         内排序是在排序整个过程中，待排序的所有记录全部放置在内存中。外排序是由于排序的记录个数太多，不能同时放置在内存中，整个过程需要在内外存之间多次交换数据才能进行。

         内部排序性能影响：时间性能、辅助空间、算法的复杂性

3 冒泡排序

         定义：冒泡排序是一种交换排序，他的基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。

毕设在线首发