排序（Sort）

• 李艳生
• 湖北师范大学
• 物理与电子科学学院
• 2020年春季

回顾

• 数组Array（随机访问，顺序存储）
• 栈Stack (后进先出)
• 队列Queue(先进先出)
• 链表LinkedList(增删高效)
• 集合Set(唯一性，无序性，确定性)
• 字典Map (键值对)
• 散列表HaspMap (查找高效)
• 树Tree（父子关系的节点集合）
• 图Graph（顶点与边的集合）

引入

一组无序的数据，如何排成有序的数据，方便各种操作？

排序的概念

• 排序是一个非常经典的问题，它以一定的顺序对一个数组（或一个列表）中的项进行重新排序（可以进行比较，例如整数，浮点数，字符串等）（增加，非递减，递减， 增加，词典等）。
• 有许多不同的排序算法，每个都有其自身的优点和局限性。
• 算法演示

排序算法

• 冒泡
• 选择
• 插入
• 归并
• 快速
• 计数
• 基数

冒泡

冒泡

• 给定一个N个元素的数组，冒泡法排序将：
  • 1.如果元素大小关系不正确，交换这两个数（在本例中为a> b）
  • 2.比较一对相邻元素（a，b）
  • 3.重复步骤1和2，直到我们到达数组的末尾
  • 4.到目前为止，最大的元素将在最后的位置。 然后我们将N减少1，并重复步骤1，直到N = 1。

冒泡

function bubbleSort(array, compareFn = defaultCompare) {
    const { length } = array; 
    for (let i = 0; i < length; i++) { 
        for (let j = 0; j < length - 1; j++) { 
            if (compareFn(array[j], array[j + 1]) === Compare.BIGGER_THAN) {
                swap(array, j, j + 1); 
            }
        }
    }
    return array;
}

const Compare = {
  LESS_THAN: -1,
  BIGGER_THAN: 1,
  EQUALS: 0
};

function defaultCompare(a, b) {
  if (a === b) {
    return Compare.EQUALS;
  }
  return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}

function swap(array, a, b) {
  /* const temp = array[a];
  array[a] = array[b];
  array[b] = temp; */
  [array[a], array[b]] = [array[b], array[a]];
}

冒泡

选择

选择

• 给定 N 个项目和 L = 0 的数组，选择排序将：
  • 1.在 [L … N-1] 范围内找出最小项目 X 的位置，
  • 2.用第 L 项交换X，
  • 3.将下限 L 增加1并重复步骤1直到 L = N-2。

选择

const selectionSort = (array, compareFn = defaultCompare) => {
  const { length } = array;
  let indexMin;
  for (let i = 0; i < length - 1; i++) {
    indexMin = i;
    // console.log('index ' + array[i]);
    for (let j = i; j < length; j++) {
      if (compareFn(array[indexMin], array[j]) === Compare.BIGGER_THAN) {
        // console.log('new index min ' + array[j]);
        indexMin = j;
      }
    }
    if (i !== indexMin) {
      // console.log('swap ' + array[i] + ' with ' + array[indexMin]);
      swap(array, i, indexMin);
    }
  }
  return array;
};

选择

插入

插入

• 插入排序类似于大多数人安排扑克牌的方式。
  • 1.从你手中的一张牌开始，
  • 2.选择下一张卡并将其插入到正确的排序顺序中，
  • 3.对所有的卡重复上一步。

插入

const insertionSort = (array, compareFn = defaultCompare) => {
  const { length } = array;
  let temp;
  for (let i = 1; i < length; i++) {
    let j = i;
    temp = array[i];
    // console.log('to be inserted ' + temp);
    while (j > 0 && 
    compareFn(array[j - 1], temp) === Compare.BIGGER_THAN) {
      // console.log('shift ' + array[j - 1]);
      array[j] = array[j - 1];
      j--;
    }
    // console.log('insert ' + temp);
    array[j] = temp;
  }
  return array;
};

插入

归并

归并

• 归并排序是分而治之的排序算法。
• 划分步骤很简单：将当前数组分成两半（如果N是偶数，则将其完全平等，或者如果N是奇数，则一边稍大于一个元素），然后递归地对这两半进行排序。

归并

• 将每对单个元素（默认情况下，已排序）归并为2个元素的有序数组，
• 将2个元素的每对有序数组归并成4个元素的有序数组，重复这个过程…，
• 最后一步：归并2个N / 2元素的排序数组，以获得完全排序的N个元素数组。

归并

function mergeSort(array, compareFn = defaultCompare) {
  if (array.length > 1) {
    const { length } = array;
    const middle = Math.floor(length / 2);
    const left = mergeSort(array.slice(0, middle), compareFn);
    const right = mergeSort(array.slice(middle, length), compareFn);
    array = merge(left, right, compareFn);
  }
  return array;
}

function merge(left, right, compareFn) {
  let i = 0;
  let j = 0;
  const result = [];
  while (i < left.length && j < right.length) {
    result.push(compareFn(left[i], right[j]) === Compare.LESS_THAN ? left[i++] : right[j++]);
  }
  return result.concat(i < left.length ? left.slice(i) : right.slice(j));
}

归并

快速

• 快速排序是另一个分而治之排序算法
• 从数组中选择一个值作为主元（pivot），也就是数组中间的那个值。
• 创建两个指针（引用），左边一个指向数组第一个值，右边一个指向数组最后一个值。移 动左指针直到我们找到一个比主元大的值，接着，移动右指针直到找到一个比主元小的值，然后 交换它们，重复这个过程，直到左指针超过了右指针。这个过程将使得比主元小的值都排在主元 之前，而比主元大的值都排在主元之后。这一步叫作划分（partition）操作。
• 算法对划分后的小数组,重复之前的两个步骤，直至数组已完全排序。

快速

快速

function quickSort(array, compareFn = defaultCompare) {
  return quick(array, 0, array.length - 1, compareFn);
}

function quick(array, left, right, compareFn) {
  let index;
  if (array.length > 1) {
    index = partition(array, left, right, compareFn);
    if (left < index - 1) {
      quick(array, left, index - 1, compareFn);
    }
    if (index < right) {
      quick(array, index, right, compareFn);
    }
  }
  return array;
}

function partition(array, left, right, compareFn) {
  const pivot = array[Math.floor((right + left) / 2)];
  let i = left;
  let j = right;

  while (i <= j) {
    while (compareFn(array[i], pivot) === Compare.LESS_THAN) {
      i++;
    }
    while (compareFn(array[j], pivot) === Compare.BIGGER_THAN) {
      j--;
    }
    if (i <= j) {
      swap(array, i, j);
      i++;
      j--;
    }
  }
  return i;
}

快速

计数

计数

• 分布式排序
• 1.找到数组中的最大值Max,并创建Max+1个元素的counts数组用于计数
• 2.迭代数组中的每个位置并在counts 数组中增加元素计数值
• 3.要迭代counts 数组并构建排序后的结果数组。

计数

function countingSort(array) {
  if (array.length < 2) {
    return array;
  }
  const maxValue = findMaxValue(array);
  let sortedIndex = 0;
  const counts = new Array(maxValue + 1);
  array.forEach(element => {
    if (!counts[element]) {
      counts[element] = 0;
    }
    counts[element]++;
  });
  // console.log('Frequencies: ' + counts.join());
  counts.forEach((element, i) => {
    while (element > 0) {
      array[sortedIndex++] = i;
      element--;
    }
  });
  return array;
}

function findMaxValue(array, compareFn = defaultCompare) {
  if (array && array.length > 0) {
    let max = array[0];
    for (let i = 1; i < array.length; i++) {
      if (compareFn(max, array[i]) === Compare.LESS_THAN) {
        max = array[i];
      }
    }
    return max;
  }
  return undefined;
}

计数

k biggest number

基数

• 基数排序也是一个分布式排序算法
• 它根据数字的有效位或基数将整数分布到桶中
• 对于十进制数，使用的基数是10，会使用10 个桶用来分布元素并且首 先基于个位数字进行排序，然后基于十位数字，然后基于百位数字，以此类推

基数

基数

function radixSort(array, radixBase = 10) {
  if (array.length < 2) {
    return array;
  }
  const minValue = findMinValue(array);
  const maxValue = findMaxValue(array);
  // Perform counting sort for each significant digit, starting at 1
  let significantDigit = 1;
  while ((maxValue - minValue) / significantDigit >= 1) {
    // console.log('radix sort for digit ' + significantDigit);
    array = countingSortForRadix(array, radixBase, significantDigit, minValue);
    // console.log(array.join());
    significantDigit *= radixBase;
  }
  return array;
}

const countingSortForRadix = (array, radixBase, significantDigit, minValue) => {
  let bucketsIndex;
  const buckets = [];
  const aux = [];
  for (let i = 0; i < radixBase; i++) {
    buckets[i] = 0;
  }
  for (let i = 0; i < array.length; i++) {
    bucketsIndex = Math.floor(((array[i] - minValue) / significantDigit) %
radixBase);
    buckets[bucketsIndex]++;
  }
  for (let i = 1; i < radixBase; i++) {
    buckets[i] += buckets[i - 1];
  }
  for (let i = array.length - 1; i >= 0; i--) {
    bucketsIndex = Math.floor(((array[i] - minValue) / significantDigit) %
radixBase);
    aux[--buckets[bucketsIndex]] = array[i];
  }
  for (let i = 0; i < array.length; i++) {
    array[i] = aux[i];
  }
  return array;
};

function findMaxValue(array, compareFn = defaultCompare) {
  if (array && array.length > 0) {
    let max = array[0];
    for (let i = 1; i < array.length; i++) {
      if (compareFn(max, array[i]) === Compare.LESS_THAN) {
        max = array[i];
      }
    }
    return max;
  }
  return undefined;
}

function findMinValue(array, compareFn = defaultCompare) {
  if (array && array.length > 0) {
    let min = array[0];
    for (let i = 1; i < array.length; i++) {
      if (compareFn(min, array[i]) === Compare.BIGGER_THAN) {
        min = array[i];
      }
    }
    return min;
  }
  return undefined;
}

基数

k - length of longest key

任务

随机产生10000个1000以内整数，分别用冒泡，选择，插入，归并，快速，计数，基数7种方法排序，并比较7种算法所用时间。