排序
一、知识点
1、排序的定义
/内排序：只在内存中进行
2、排序的分类
\外排序：与内外存进行排序
内排序： /直接插入排序
1）插入排序
\shell排序
/冒泡排序
2）交换排序
\快速排序
/简单选择排序
3）选择排序 堆
\ 锦标赛排序
4）归并排序（二路）
5）基数排序（多关链字排序）
3、时间复杂度（上午题目常考，不会求也得记住啊兄弟姐妹们！）
* * * * * * 15 * * * 15 * * *
/稳定 * * * * * * * * 15 15 * * * *(前后不变)
排序
\ 不稳定 * * * * * * * * 15 15 * * * *(前后改变)
经整理得:选择、希尔、堆、快速排序是不稳定的；直接插入、冒泡、合并排序是稳定的。
●锦标赛排序方法： 13 16 11 18 21 3 17 6
\ / \ / \ / \ /
13 11 3 6
\ / \ /
11 3
\ /
3（胜出，将其拿出，并令其为正无穷&Go On）
●归并排序方法： 13 16 11 18 21 3 17 6
\ / \ / \ / \ /
13,16 11,18 3,21 6,17
\ / \ /
11,13,16,18 3,6,17,21
\ /
3,6,11,13,16,17,18,21
●shell排序算法：1）定义一个步长（或者说增量）数组D[m]；其中：D[m-1]=1(最后一个增量必须为1，否则可能不完全)
2）共排m趟，其中第i趟增量为D[i],把整个序列分成D[i]个子序列，分别对这D[i]个子序列进行直接插入排序。
程序如下： for(i=0;i<m;i++)
{for(j=0;j<d[i];j++)
{对第i个子序列进行直接插入排序；
注意：下标之差为D[i];
}
}
●快速排序 ( smaller )data ( bigger )
d[] i-> 13 16 11 18 21 3 17 6 24 8 <-j
先从后往前找，再从前往后找。
思想：空一个插入一个，i空j挪，j空i挪（这里的i,j是指i,j两指针所指的下标）。
一次执行算法：1）令temp=d[0](枢纽)，i=0,j=n-1;
2）奇数次时从j位置出发向前找第一个比temp小的元素，找到后放到i的位置(d[i]=d[j];i++;) i往后挪。
3）偶数次时从i开始往后找第一个比temp大的数，（d[j]=d[i];j--;)
4）当i=j时，结束循环。d[i]=temp；
再用递归对左右进行快速排序，因为快速排序是一个典型的递归算法。
●堆排序
定义：d[n]满足条件：d[i]<d[2i+1]&&d[i]<d[2i+2] 大堆（上大下小）
d[i]>d[2i+1]&&d[i]>d[2i+2] 小堆（上小下大）
判断是否为堆应该将其转换成树的形式。总共排序n-1次
上一页 [1] [2] [3] 下一页
上一篇文章： 考试辅导：程序员数据结构笔记（二）下一篇文章： 考试辅导：程序员数据结构笔记（三） 【
发表评论】【
加入收藏】【
告诉好友】【
打印此文】【
关闭窗口】
