数组排序

这篇文章简单介绍一下基本的排序, 语言是swift

一, 冒泡排序

        for i in 0..<array.count - 1 {
          //因为是判断当前位置元素, 和下一位置的元素, 所以范围为(0 - 数组长度减1)
            var j = 0
            while j < array.count - 1 - i {
                if array[j] > array[j + 1] {
                    let temp = array[j]
                    array[j] = array[j + 1]
                    array[j + 1] = temp
                }
                j = j + 1
            }
        }

总结 : 冒泡排序的原理是每次循环结束后都把最大值, 或者最小值放在末尾, 直到遍历结束, 每层循环数为 n-2 , n-3, n-4, 1.

二, 选择排序

        for i in 0..<array.count - 1 {
            var j = i + 1
            while j < array.count {
                if array[i] > array[j] {
                    let temp = array[i]
                    array[i] = array[j]
                    array[j] = temp
                }
                
                j = j + 1;
            }
        }

总结 : 选择排序的原理是每次循环都把最小值或最大值放在本层循环的首位, 每层循环数为n-2 , n-3, n-4, 1.

三, 插入排序

//
//        //1. 先用temp保存25, j = 1, 然后判断25是否小于15, 不大于则直接将array[1] = temp即(25), 此时数据不变
//        //2. 先用temp保存5,
//        //此时j = 2, 然后判断5是否小于25, 小于则将array[2] = 25,      当前为15,25,25,95,85
//        //此时j = 1, 然后继续判断5是否小于15, 小于则将array[1] = 15,   当前为15,15,25,95,85
//        //此时j = 0, 不继续判断while循环条件, 则将array[0] = temp(5), 当前为5, 15,25,95,85
//
        //依次类推

        for i in 1..<array.count {
            //临时存储值
            let temp = array[i]

            var j = i
            //如果比前一个值小 则互换位置
            while j > 0 , temp < array[j - 1] {
                array[j] = array[j - 1]
                j = j - 1
                print(array)
            }
            //把存储的值附上, 得到的j必然是本轮循环的第一个位置
            array[j] = temp
        }

四, 希尔排序 (效率最高, 但是有不稳定性)

void shellSort (NSMutableArray *array) {
  int count = (int)array.count;
  //初始增量为数组长度的一半，然后每次除以2取整
  for (int increment = count/2; increment>0; increment /=2) {
  //初始下标设为第一个增量的位置，然后递增
    for (int i = increment; i<count; i++) {
        //获取当前位置
        int j = i;
        //然后将此位置之前的元素，按照增量进行跳跃式比较
        while (j-increment>=0 && array[j]<array[j-increment]) {
            [array exchangeObjectAtIndex:j withObjectAtIndex:j-increment];
            j-=increment;
        }
    }
  }
}