基本排序

冒泡 O(n^2)

1. 比较数组中第一个元素和第二个元素的大小，如果第一个元素比第二个元素大，那么交换它们的位置。如果第一个元素比第二个元素小，那么不做任何操作。

2. 再比较第二个元素和第三个元素，如果第二个元素比第三个元素大，那么交换它们的位置。反之，也不做任何操作。

3. 以此类推，直到比较完倒数第二个元素和倒数第一个元素。此时，整个数组里面最大的元素已经被移到了数组的末尾。

4. 再在除最后一个元素的剩余元素中重复以上操作。

5. 当最后只剩第一个元素和第二个元素需要操作的时候，比较它们的大小并根据需要决定是否交换它们的位置。结束后，整个排序结束。

arr = [1,3,5,7,9,8,6,4,2,0]
for i in 0...arr.size-1
    for j in i + 1..arr.size-1
        arr[i], arr[j] = arr[j], arr[i] if arr[i] > arr[j]
    end
end
arr

选择排序 O(n^2)

1. 从数组中找出值最小的元素。

2. 将最小的这个元素与数组的首个元素互换位置。

3. 然后再从剩余的元素中找最小的元素

4. 将它与整个数组的第二个元素互换位置。

5. 以此类推，直到整个最后只剩一个未被选择的元素。此时数组已经有序，排序结束

arr = [1,3,5,7,9,8,6,4,2,0]
for i in 0...arr.size - 1
    min = i
    for j in i..arr.size - 1
        min = j if arr[min] > arr[j]
    end
    arr[i], arr[min] = arr[min], arr[i]
end

插入排序

1. 首先将数组的首个元素视作已经排序完成。

2. 将第二个元素与首个元素比较，如果第二个元素小于第一个元素，则将第二个元素插入第一个元素之前。反之则不做任何操作。操作完成后，将数组前两个元素视作排序完成。

3. 将第三个元素依次与前两个元素比较，并视其大小将其插入到前面元素中合适的位置。插入完成后将前三个元素都视作排序完成。

4. 依次类推，等数组所有元素都插入到合适的位置后，排序结束。

arr = [1,3,5,7,9,8,6,4,2,0]
for i in 1...arr.size
    for j in 0..i
         arr[j], arr[i] = arr[i], arr[j] if arr[i] < arr[j]
    end
end

归并排序

归并排序，顾名思义就是通过将初始数组拆分成数个子数组，然后再将子数组重新合并起来，在合并的过程中，将较小的元素放在前面，较大的元素放在后面，从而实现排序

快排 O(nlogn)

快速排序首先从数组中随机选取一个值作为基准值，然后通过比较，在遍历完一次数组后，总是将数组切分为“比基准值小的 + 基准值 + 比基准值大”的三部分。而且，每次遍历完成后，基准值总是会被交换到它应该在的位置上。然后再在比基准值小的部分中重新随机选取基准值、再切分、再选值，在比基准值大的部分中也同样操作。最后实现整个数组的有序。

arr = [1,3,5,7,9,8,6,4,2,0]

def sort(arr)
      left_mark_temp = [1]                  # 用来保存切分后两个数组的起始元素在初始数组中的位置
      right_mark_temp = [arr.length - 1]    # 用来保存切分后两个数组的末尾元素在初始数组中的位置
      while right_mark_temp.length != 0
        left = left_mark_temp.pop           # 取出一个数组的开头
        right = right_mark_temp.pop         # 取出一个数组的末尾
        pivot = left – 1                   # 选取切分这个数组的基准值
        last = right
        while last > pivot                  # 如果取出的数组中只含有一个元素，就不进行任何操作
          while right > pivot               # 将右指针向左移动 
            break if arr[right] < arr[pivot] # 遇到比基准值小的元素停止移动
            right -= 1
          end
          while left < right # 将左指针向右移动
            break if arr[left] > arr[pivot] # 遇到比基准值大的元素停止移动
            left += 1
          end
          if left >= right                  # 如果左右指针相遇
            arr[pivot], arr[right] = arr[right], arr[pivot] # 交换基准值和右指针的元素
            left_mark_temp << pivot + 1     # 保存切分后前半部分数组的起始元素
            left_mark_temp << right + 2     # 保存切分后后半部分数组的起始元素
            right_mark_temp << right – 1   # 保存切分后前半部分数组的末尾元素
            right_mark_temp << last         # 保存切分后后半部分数组的末尾元素
            break                           # 开始下一轮的切分
          end
          arr[left], arr[right] = arr[right], arr[left] # 如果左右指针未相遇，则交换左右指针指向的元素
        end
      end
    end
  end
end