算法-排序

最近将之前的算法知识进行梳理，总结了几种常见的排序算法。废话不多说，上图上代码，看解析

冒泡排序

原理：
1.临近的数字两两进行比较,按照从小到大或者从大到小的顺序进行交换。
2.这样一趟过去后,最大或最小的数字被交换到了最后一位。
3.然后再从头开始进行两两比较交换,直到倒数第二位时结束。

void bubble_sort(int a[], int n)
{
    int i,j,temp;
    for (j = 0; j < n-1; j++) {
        for (i = 0; i < n - 1 - j; i++) {
            if (a[i] > a[i + 1]) {
                temp = a[I];
                a[i] = a[i + 1];
                a[i + 1] = temp;
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        
        int a[6] = {9,6,2,7,1,8};
        bubble_sort(a, 6);
        
    }
    return 0;
}

bubble_sort

快速排序

原理：
快速排序是对冒泡排序的一种改进，基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对两部分记录继续进行排序。

void quick_sort(int *a, int left, int right)
{
    if(left > right){
        return;
    }
    int i = left;
    int j = right;
    int key = a[left];
    while (i < j) {
        while (i < j && key <= a[j]) {
            j--;
        }
        a[i] = a[j];
        while (i < j && key >= a[i]) {
            I++;
        }
        a[j] = a[I];
    }
    a[i] = key;
    //两边分别递归
    quick_sort(a, left, i - 1);
    quick_sort(a, i + 1, right);
}

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        
        int a[6] = {6,2,7,3,8,9};
        //第二个参数：起始索引
        //第三个参数：结束索引
        quick_sort(a,0,5);

    }
    return 0;
}

创建变量i=0（指向第一个数据）, j=5(指向最后一个数据), k=6(赋值为第一个数据的值)。

quick_sort

选择排序

原理：
从所有序列中先找到最小的，然后放到第一个位置。之后再看剩余元素中最小的，放到第二个位置……以此类推，就可以完成整个的排序工作了。

void select_sort(int a[], int n)
{
    for (int i = 0; i < n; i++) {
        int temp = 0;
        int min = a[I];
        int index = I;
        for (int j = i + 1; j < n; j++) {
            if (a[j] < min) {
                min = a[j];
                index = j;
            }
        }
        temp = a[I];
        a[i] = min;
        a[index] = temp;
    }
}

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        
        int a[6] = {9,6,2,7,1,8};
        select_sort(a,6);
        
    }
    return 0;
}

select_sort

归并排序

原理：
用二分法将数组分割，直到每个分组里都只有一个元素。所以此时我们就得到了若干个有序数组。（每个数组里只有一个元素）

NSMutableArray * array = [NSMutableArray arrayWithObjects:@6,@1,@7,@5,@8,@2,@4,@3, nil];
//调用排序
[self mergeSortArray:array];

- (void)mergeSortArray:(NSMutableArray *)array {
    //创建一个副本数组
    NSMutableArray * auxiliaryArray = [[NSMutableArray alloc]initWithCapacity:array.count];
    
    //对数组进行第一次二分，初始范围为0到array.count-1
    [self mergeSort:array auxiliary:auxiliaryArray low:0 high:array.count-1];
}

- (void)mergeSort:(NSMutableArray *)array auxiliary:(NSMutableArray *)auxiliaryArray low:(int)low high:(int)high {
    //递归跳出判断
    if (low>=high) {
        return;
    }
    //对分组进行二分
    int middle = (high - low)/2 + low;
    
    //对左侧的分组进行递归二分 low为第一个元素索引，middle为最后一个元素索引
    [self mergeSort:array auxiliary:auxiliaryArray low:low high:middle];
    
    //对右侧的分组进行递归二分 middle+1为第一个元素的索引，high为最后一个元素的索引
    [self mergeSort:array auxiliary:auxiliaryArray low:middle + 1 high:high];
    
    //对每个有序数组进行回归合并
    [self merge:array auxiliary:auxiliaryArray low:low middel:middle high:high];
}

- (void)merge:(NSMutableArray *)array auxiliary:(NSMutableArray *)auxiliaryArray low:(int)low middel:(int)middle high:(int)high {
    //将数组元素复制到副本
    for (int i=low; i<=high; i++) {
        auxiliaryArray[i] = array[I];
    }
    //左侧数组标记
    int leftIndex = low;
    //右侧数组标记
    int rightIndex = middle + 1;
    
    //比较完成后比较小的元素要放的位置标记
    int currentIndex = low;
    
    while (leftIndex <= middle && rightIndex <= high) {
        //此处是使用NSNumber进行的比较，你也可以转成NSInteger再比较
        if ([auxiliaryArray[leftIndex] compare:auxiliaryArray[rightIndex]]!=NSOrderedDescending) {
            //左侧标记的元素小于等于右侧标记的元素
            array[currentIndex] = auxiliaryArray[leftIndex];
            currentIndex++;
            leftIndex++;
        }else{
            //右侧标记的元素小于左侧标记的元素
            array[currentIndex] = auxiliaryArray[rightIndex];
            currentIndex++;
            rightIndex++;
        }
    }
    //如果完成后左侧数组有剩余
    if (leftIndex <= middle) {
        for (int i = 0; i<=middle - leftIndex; i++) {
            array[currentIndex +i] = auxiliaryArray[leftIndex +I ];
        }
    }
}

将两个有序数组合并为一个数组

合并两个有序数组

归并排序

merge_sort

总结

在实际应用中，根据需求选择合适的排序算法。
其他常用的排序算法还有：插入排序，堆排序，桶排序。