排序算法

排序算法

• 说实在的，这些算法都是应付面试用的，真正的iOS开发过程中，苹果都帮我们封装好了相对应的方法，简单省时省力，效率还高。当然了，研究算法可以提升自己的编程思想，以下案例都是从小到大排序

选择排序

• 取出第i个元素，依次和i后面的每一个元素对比，如果i+1元素比i元素小，那么交换元素值，然后接着拿交换后的元素值进行对比，直到对比到最后一个元素，其他元素以此类推

// 选择排序
int nums[8] = {99, 123, 22, 6, 2, 55, 67, 100};
// 计算长度
int length = sizeof(nums) / sizeof(nums[0]);
for (int i = 0; i < length; i++) {
    for (int j = i + 1; j < length; j++) {
        if(nums[i] > nums[j]){
            // 交换元素值
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }
}

冒泡排序

• 冒泡排序，就是用相邻的两个元素比较，每完全比较一次，最值就会出现在末尾
• 1和2，2和3，3和4.........以此类推

// 冒泡排序
int nums[8] = {99, 123, 22, 6, 2, 55, 67, 100};
int length = sizeof(nums) / sizeof(nums[0]);
for(int i = 0; i < length - 1; i++){
    for (int j = 0; j < length - 1 - i; j++) {
        if(nums[j] > nums[j + 1]){
            int temp = nums[j];
            nums[j] = nums[j + 1];
            nums[j + 1] = temp;
        }
    }
}

折半查找

• 数组必须是有序的
• 必须已知min和max（知道范围）
• 动态计算mid的值，取出mid对应的值进行比较
• 如果mid对应的值大于需要查找的值，那么max = mid - 1
• 如果mid对应的值小于需要查找的值，那么min = mid + 1

// 折半查找第一种方式
int findKey1(int nums[], int length, int key)
{
    int min, max, mid;
    min = 0;
    max = length - 1;
    mid = (min + max) / 2;

    while (key != nums[mid]) {
        if (key > nums[mid]) {
            // 判断如果要找的值，大于了取出的值，那么min要改变
            min = mid + 1;
        }else if(key < nums[mid]){
            // 判断如果要找的值，小雨了取出的值，那么max要改变
            max = mid - 1;
        }

        // 超出范围,数组中没有要查找的值
        if(min > max){
            return  -1;
        }
        mid = (max + min) / 2;
    }
    return mid;
}

// 折半查找第二种方式
int findKey2(int nums[], int length, int key)
{
    int min, max, mid;
    min = 0;
    max = length - 1;

    // 只要还在范围内就需要查找
    while (min <= max) {
        // 计算中间值
        mid = (max + min) / 2;
        if(key > nums[mid]){
            min = mid + 1;
        }else if(key < nums[mid]){
            max = mid - 1;
        }else{
            return mid;
        }
    }
    return  -1;
}