（插入排序、选择排序、交换排序、归并排序、基数排序）
排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。
我们这里说说八大排序就是内部排序。
1342514529_5795.jpg
自己用iOS写了几个排序，先来个数组：
NSMutableArray *array = [NSMutableArray arrayWithObjects:@89,@2,@22,@95,@88,@66,@43,@31,@57, nil];
1、直接插入排序
思路：将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。
图示：
1342520948_8667.jpg
代码：
-(void)sortingForInsertWithArray:(NSMutableArray *)array{
for (int i = 1; i<=array.count-1; i++) {
if (array[i-1] > array[i]) {
int j = i-1;
id temp = array[i];
array[i] = array[i-1];
while (j>=0&&temp<array[j]) {
array[j+1] = array[j];
j--;
}
array[j+1] = temp;
}
}
}
2、希尔排序
思路：希尔排序是1959 年由D.L.Shell 提出来的，相对直接排序有较大的改进。希尔排序又叫缩小增量排序。
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
图示：
1342577299_5077.jpg
代码：
-(void)sortingForShellWithArray:(NSMutableArray *)array{
int dk = (int)(array.count-1)/2;
while (dk>=1) {
[self shellSortingWithArray:array startIndex:dk];
dk = dk/2;
}
}
-(void)shellSortingWithArray:(NSMutableArray *)array startIndex:(int)dk{
for (int i = dk; i<=array.count-1; i+=dk) {
if (array[i]<array[i-dk]) {
int j = i-dk;
id temp = array[i];
array[i] = array[i - dk];
while (j>=0&&temp<array[j]) {
array[j+dk] = array[j];
j-=dk;
}
array[j+dk] = temp;
}
}
}
3、简单选择排序
思路：在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。
图示：
1342586432_7130.jpg
代码：
-(void)sortingForSelectWithArray:(NSMutableArray *)array{
int i,j,k;
for (i = 0; i<=array.count-1; i++) {
k = i;
for (j = i+1; j<=array.count-1; j++) {
if (array[k] >array[j] ) {
k = j;
}
}
if (k!=i) {
id temp = array[i];
array[i]= array[k];
array[k]= temp;
}
}
}
4、堆排序
思路：堆排序是一种树形选择排序，是对直接选择排序的有效改进。
堆的定义如下：具有n个元素的序列（k1,k2,...,kn),当且仅当满足
时称之为堆。由堆的定义可以看出，堆顶元素（即第一个元素）必为最小项（小顶堆）。若以一维数组存储一个堆，则堆对应一棵完全二叉树，且所有非叶结点的值均不大于(或不小于)其子女的值，根结点（堆顶元素）的值是最小(或最大)的。如：（a）大顶堆序列：（96, 83,27,38,11,09)
(b) 小顶堆序列：（12，36，24，85，47，30，53，91）
初始时把要排序的n个数的序列看作是一棵顺序存储的二叉树（一维数组存储二叉树），调整它们的存储序，使之成为一个堆，将堆顶元素输出，得到n 个元素中最小(或最大)的元素，这时堆的根节点的数最小（或者最大）。然后对前面(n-1)个元素重新调整使之成为堆，输出堆顶元素，得到n 个元素中次小(或次大)的元素。依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。称这个过程为堆排序。
代码：
-(void)sortingForHeapWithArray:(NSMutableArray *)array{
for (int i = (int)(array.count -1)/2; i>=0; --i) {
[self heapSortingWithArray:array startIndex:i arrayifCount:(int)array.count-1];
}
for (int i = (int)array.count-1; i>0; --i) {
id temp = array[i];
array[i] = array[0];
array[0] = temp;
[self heapSortingWithArray:array startIndex:0 arrayifCount:i];
}
}
-(void)heapSortingWithArray:(NSMutableArray *)array startIndex:(int)startIndex arrayifCount:(int)count{
id temp = array[startIndex];
int child = 2*startIndex +1;
while (child<count) {
if (child+1<count &&array[child]<array[child+1]) {
++child;
}
if (array[startIndex]<array[child]) {
array[startIndex] = array[child];
startIndex = child;
child = 2*startIndex+1;
}else{
break;
}
array[startIndex] = temp;
}
}
5、冒泡排序
思路：在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。
图示：
1342782078_9990.jpg
代码：
-(void)sortingForBubblingWithArray:(NSMutableArray *)array{
for (int i=0; i<=array.count-1; i++) {
for (int j=0; j<array.count-1-i; j++) {
if (array[j] < array[j+1] ) {
id string = array[j];
array[j]= array[j+1];
array[j+1] = string;
}
}
}
}
6、快速排序
思路：1）选择一个基准元素,通常选择第一个元素或者最后一个元素,
2）通过一趟排序讲待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小。另一部分记录的 元素值比基准值大。
3）此时基准元素在其排好序后的正确位置
4）然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。
图示：
a）一趟排序：
1342782317_4426.jpg
b）排序全程：
1342782329_8314.jpg
代码：
-(void)sortingForFastWithArray:(NSMutableArray *)array strartIndex:(int)strartIndex endIndex:(int)endIndex{
if (strartIndex>endIndex) {
return;
}
int i = strartIndex, j = endIndex;
id key = array[strartIndex];
while (i<j) {
while (i<j && key>=array[j]) {
j--;
}
array[i] = array[j];
while (i<j && key<=array[i]) {
i++;
}
array[j] = array[i];
}
array[i] = key;
[self sortingForFastWithArray:array strartIndex:strartIndex endIndex:i-1];
[self sortingForFastWithArray:array strartIndex:i+1 endIndex:endIndex];
}
7、归并排序
思路：归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
图示：
1342842633_6751.jpg
代码：
-(void)sortingForMergeWithArray:(NSMutableArray *)array standbyArray:(NSMutableArray *)newArray startIndex:(int)startIndex endIndex:(int)endIndex{
int middle;
if (startIndex<endIndex) {
middle = (startIndex +endIndex)/2;
[self sortingForMergeWithArray:array standbyArray:newArray startIndex:startIndex endIndex:middle];
[self sortingForMergeWithArray:array standbyArray:newArray startIndex:middle+1 endIndex:endIndex];
int i = startIndex,
j = middle+1,
k = startIndex;
while (i!=middle+1 && j!=endIndex +1) {
if (array[i]>=array[j]) {
newArray[k++] = array[j++];
}else{
newArray[k++] = array[i++];
}
}
while (i!=middle+1) {
newArray[k++] = array[i++];
}
while (j!=endIndex+1) {
newArray[k++] = array[j++];
}
for (i = startIndex; i<=endIndex; i++) {
array[i] = newArray[i];
}
}
}
网友评论