从大类分，排序分为外排序和内排序。内外排序的区别在于是否需要多次从内存外读取数据进行排序。外排序是要多次从外存读取数据到内存。而内排序是一次性读到内存中进行排序。
从算法的稳定性来说，排序分为稳定排序和非稳定排序。非稳定排序是指对于两个相同大小的元素，多次进行排序，其所在位置不一定相同。而稳定排序是指，对于每一个元素，每一次排序后所在的位置都是确定的。
从排序的操作，可以大致如下区分
QQ20200519-210256.png
其中冒泡，简单选择，直接插入都是属于简单算法，相对适用于数量比较少的数组排序，实现也较为简单。
而希尔排序，归并排序，堆排序，快速排序属于改进的排序算法。相对适用于较为多的数组排序，改进的排序算法中，只有归并排序是稳定排序，如果对数组的排序稳定性有要求，建议使用归并排序。
各个算法的时间复习度如下
9-0-3.jpg
下面由简单到困难，去实现几个算法
冒泡排序
中心思想：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止
代码实现
+(NSMutableArray *)bubbleSort:(NSMutableArray *)array withOrderType:(OrderType)orderType{
BOOL isSwap = YES;//某一次循环是否有交换，如果没有交换，则代表着往后的数组有序，则不用再冒泡替换
for (int i = 0; i < array.count-1 && isSwap; i++) {
isSwap = NO;
for ( int j = (int)array.count - 1; j > i; j--) {
// NSNumber *numberA = array[j];
// NSNumber *numberB = array[j-1];
if(orderType == OrderType_Aesc){
if([array[j] intValue] < [array[j-1] intValue]){
[array swapFrom:j toIndex:j-1];
isSwap = YES;
}
//
}else if(orderType == OrderType_Desc){
if([array[j] intValue] > [array[j-1] intValue]){
[array swapFrom:j toIndex:j-1];
isSwap = YES;
}
}
}
}
return array;
}
简单选择排序
中心思想：简单选择排序法（Simple Selection Sort）就是通过n-i次关键字间的比较，从n-i＋1个记录中选出关键字最小的记录，并和第i（1≤i≤n）个记录交换之
代码实现
/// 简单选择排序
/// 中心思想：通过n-1次比较，计算出n个个元素中最小或是最大的值，然后放在最前方，就能确保最前方的值最小或是最大
/// 如[@39,@434,@1,@34,@32,@9],这个数组，
/// 从第一个未排序元素开始，循环比对，计算出最小或是最大的值，然后放到最前方
/// 循环上方的操作，就能依次把最大或是最小的数放在最前方
/// 对比冒泡排序，减少了交互次数，但是比对次数没有减少
/// @param array 待排序数组
/// @param orderType 排序方式
+(NSMutableArray *)simpleSelectionSort:(NSMutableArray *)array withOrderType:(OrderType)orderType{
for (int i = 0; i < array.count; i++) {
int minIndex = I;
for (int j = i+1; j < array.count; j++) {
// NSNumber *numberA = array[minIndex];
// NSNumber *numberB = array[j];
if(orderType == OrderType_Aesc){
if([array[minIndex] intValue] > [array[j] intValue]){
minIndex = j;
}
//
}else if(orderType == OrderType_Desc){
if([array[minIndex] intValue] < [array[j] intValue]){
minIndex = j;
}
}
}
if(minIndex != i){
[array swapFrom:minIndex toIndex:i];
}
}
return array;
}
直接插入排序
中心思想：将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表
代码实现
/// 直接插入排序
/// 中心思想，从小到大排列，如果一个元素A与前方有序数组坐比较，如果元素比前方有序数组小，则有序数组一个一个往后挪，直到数组里面某一个元素B不大于元素A时候，A插入到B后面
/// 如果数组基本有序的时候，这个方案比较有优势，不需要做太多比较和数据交互
/// @param array <#array description#>
/// @param orderType <#orderType description#>
+(NSMutableArray *)stragightInsertionSort:(NSMutableArray *)array withOrderType:(OrderType)orderType{
NSNumber *temp = @0;
for (int i = 1; i < array.count; i++) {
if(orderType == OrderType_Aesc){
//从原数组的第二个元素开始，每一个元素和前面的元素的做比较
if ([array[i] intValue] < [array[i - 1] intValue] ) {
//如果该元素比前一个元素小，则将值存入temp元素当中，用temp和前面的元素做对比，如果少于前面的元素，前面的元素一个一个往后挪。直到前面的元素不大于temp元素时，则停止挪动元素
temp = array[I];
int j;
for ( j = i - 1; j >= 0 && [array[j] intValue] > [temp intValue] ; j--) {
array[j+1] = array[j];
}
array[j+1] = temp;
}
}else if(orderType == OrderType_Desc){
//从第二个元素开始，
if ([array[i] intValue] > [array[i - 1] intValue] ) {
temp = array[I];
int j;
for ( j = i - 1; j >= 0 && [array[j] intValue] < [temp intValue] ; j--) {
array[j+1] = array[j];
}
array[j+1] = temp;
}
}
}
return array;
}
希尔排序
中心思想： 将待排序的数据按照一定的间隔n，将间隔n的元素组成一个子数组，对子数组进行直接插入排序，使子数组有序，
代码实现
/// 希尔排序O(n^(1.3—2))
/// 中心思想:
/// 将待排序的数据按照一定的间隔n，将间隔n的元素组成一个子数组，对子数组进行直接插入排序，使子数组有序，
/// 随着n不断减少，原来待数组越来越接近有序
/// 当n= 1的时候，相当于对整个数组已经有序
/// 如果数组基本有序且数组数量比较少时候，这个方案比较有优势，不需要做太多比较和挪动
/// @param array <#array description#>
/// @param orderType <#orderType description#>
+(NSMutableArray *)shellSort:(NSMutableArray *)array withOrderType:(OrderType)orderType{
NSNumber *temp = @0;
int increment = (int)array.count;
while (increment > 1) {
increment = increment/3 + 1;
if(orderType == OrderType_Aesc){
for (int i = increment ; i < array.count; i++) {
if ([array[i] intValue] < [array[i - increment] intValue] ) {
//如果该元素比前一个元素小，则将值存入temp元素当中，用temp和前面的元素做对比，如果少于前面的元素，前面的元素一个一个往后挪。直到前面的元素不大于temp元素时，则停止挪动元素
temp = array[I];
int j;
for ( j = i - increment; j >= 0 && [array[j] intValue] > [temp intValue] ; j = j - increment) {
array[j+increment] = array[j];
}
array[j+increment] = temp;
}
}
}else if(orderType == OrderType_Desc){
for (int i = increment ; i < array.count; i++) {
if ([array[i] intValue] > [array[i - increment] intValue] ) {
//如果该元素比前一个元素小，则将值存入temp元素当中，用temp和前面的元素做对比，如果少于前面的元素，前面的元素一个一个往后挪。直到前面的元素不大于temp元素时，则停止挪动元素
temp = array[I];
int j;
for ( j = i - increment; j >= 0 && [array[j] intValue] < [temp intValue] ; j = j - increment) {
array[j+increment] = array[j];
}
array[j+increment] = temp;
}
}
}
}
return array;
}
归并排序
中心思想：分治策略，将问题不断的缩小，
通过将数组不断采用二分法分成子数组，对子数组进行排序，从而实现数组整体有序
代码实现
/// 归并排序
/// 中心思想：分治策略，将问题不断的缩小，
/// 通过将数组不断采用二分法分成子数组，对子数组进行排序，从而实现数组整体有序
/// @param array <#array description#>
/// @param orderType <#orderType description#>
+(NSMutableArray *)mergeSort:(NSMutableArray *)array withOrderType:(OrderType)orderType{
NSMutableArray *tempArray = [array mutableCopy];
[SortTool mergeSubSort:array withBegin:0 withEnd:(int)array.count - 1 withTempArray:tempArray withOrderType:orderType];
return array;
}
/// 递归对数组进行二分，然后再对子数组进行排序
/// @param array <#array description#>
/// @param beginIndex <#beginIndex description#>
/// @param endIndex <#endIndex description#>
/// @param tempArray <#tempArray description#>
/// @param orderType <#orderType description#>
+(void)mergeSubSort:(NSMutableArray *)array withBegin:(int)beginIndex withEnd:(int)endIndex withTempArray:(NSMutableArray *)tempArray withOrderType:(OrderType)orderType{
if(beginIndex < endIndex){
int midIndex = (beginIndex + endIndex )/2;
[SortTool mergeSubSort:array withBegin:beginIndex withEnd:midIndex withTempArray:tempArray withOrderType:orderType];
[SortTool mergeSubSort:array withBegin:midIndex+1 withEnd:endIndex withTempArray:tempArray withOrderType:orderType];
[SortTool mergeArray:array withBegin:beginIndex withEnd:endIndex withTempArray:tempArray withOrderType:orderType];
}else{
array[beginIndex] = array[endIndex];
}
}
///
/// @param array <#array description#>
/// @param beginIndex <#beginIndex description#>
/// @param endIndex <#endIndex description#>
/// @param tempArray <#tempArray description#>
/// @param orderType <#orderType description#>
+(void)mergeArray:(NSMutableArray *)array withBegin:(int)beginIndex withEnd:(int)endIndex withTempArray:(NSMutableArray *)tempArray withOrderType:(OrderType)orderType{
//获取中间做表
int midIndex = (beginIndex+endIndex)/2;
//比较中间坐标两边的数据，将小的放前面
int i,j,k;
for ( i = beginIndex, j = midIndex+1 ,k = i; i <= midIndex && j <= endIndex;k++ ) {
if(orderType == OrderType_Aesc){
if([array[i] intValue] < [array[j] intValue]){
tempArray[k] = array[I];
i = i + 1;
}else{
tempArray[k] = array[j];
j = j + 1;
}
}else{
if([array[i] intValue] > [array[j] intValue]){
tempArray[k] = array[I];
i = i + 1;
}else{
tempArray[k] = array[j];
j = j + 1;
}
}
}
//如果右边的数据已经全部放入暂存数组，则把左边剩余的放入到暂存数组
if(i <= midIndex){
for (int l = 0; l <= midIndex - i; l++,k++) {
tempArray[k] = array[i+l];
}
}
//如果左边的数据已经全部放入暂存数组，则把右边剩余的放入到暂存数组
if(j <= endIndex){
for (int l = 0; l <= endIndex - j; l++,k++) {
tempArray[k] = array[j+l];
}
}
//将暂存数组排好序的部分替换到需要排序的数组中去
while (beginIndex <= endIndex) {
array[beginIndex] = tempArray[beginIndex];
beginIndex = beginIndex + 1;
}
}
快速排序
中心思想：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的
代码实现
/// 中心思想：确定一个中枢值，把按大小把数组拆分成左右两个数组，通过递归，把数组不断拆分，以达到排序的目的
/// @param array <#array description#>
/// @param orderType <#orderType description#>
+(NSMutableArray *)quickSort:(NSMutableArray *)array withOrderType:(OrderType)orderType{
[SortTool quickSort:array withBeginIndex:0 withEndIndex:(int)array.count -1 withOrderType:orderType];
return array;
}
+(void)quickSort:(NSMutableArray *)array withBeginIndex:(int)beginInex withEndIndex:(int)endIndex withOrderType:(OrderType)orderType{
if(beginInex < endIndex){
//确定中枢，并按照中枢值分左右两个数组，对左右两个数组排序
int privot = [SortTool makePivot:array withBeginIndex:beginInex withEndIndex:endIndex withOrderType:orderType];
[SortTool quickSort:array withBeginIndex:beginInex withEndIndex:privot-1 withOrderType:orderType];
[SortTool quickSort:array withBeginIndex:privot + 1 withEndIndex:endIndex withOrderType:orderType];
}
}
+(int)makePivot:(NSMutableArray *)array withBeginIndex:(int)beginInex withEndIndex:(int)endIndex withOrderType:(OrderType)orderType{
//取第一个值为中枢值，然后从首尾两端循环对比。根据大小把数组放在中枢的两边
int privotValue = [array[beginInex] intValue];
while (beginInex < endIndex) {
if(orderType == OrderType_Aesc){
while(beginInex < endIndex && privotValue <= [array[endIndex] intValue]){
endIndex = endIndex - 1;
}
[array swapFrom:beginInex toIndex:endIndex];
while(beginInex < endIndex && [array[beginInex] intValue] <= privotValue){
beginInex = beginInex + 1;
}
[array swapFrom:beginInex toIndex:endIndex];
}else if(orderType == OrderType_Desc){
while(beginInex < endIndex && privotValue >= [array[endIndex] intValue]){
endIndex = endIndex - 1;
}
[array swapFrom:beginInex toIndex:endIndex];
while(beginInex < endIndex && [array[beginInex] intValue] >= privotValue){
beginInex = beginInex + 1;
}
[array swapFrom:beginInex toIndex:endIndex];
}
}
return beginInex;
}
网友评论