Dart 实现几种常见的排序算法-一一网

这是我参与更文挑战的第1天，活动详情查看：更文挑战

前言

网络上 Java、JS 等其他语言的算法实现到处可见，本文主要是使用 Dart 实现这几种常见的排序算法，算是做个回顾总结。

我是 Zero，下面代码中我添加了非常详细的注释，可以收藏慢慢看哦

冒泡排序

示例图

代码实现

/// 冒泡排序
List<int> bubbleSort(List<int> arr) {
  //遍历所有元素
  for (var i = 0; i < arr.length; ++i) {
    //从第二个元素开始遍历
    for (var j = i + 1; j < arr.length; ++j) {
      //取出j位值
      int temp = arr[j];
      //j位值和i位值比较，小于则交换位置，放到前面
      if (temp < arr[i]) {
        //先把i位值放到j位上
        arr[j] = arr[i];
        //再把临时j位值，放到i位上
        arr[i] = temp;
      }
    }
  }
  return arr;
}
复制代码

插入排序

示例图

插入排序

代码实现

///插入排序
List<int> insertionSort(List<int> arr) {
  for (var i = 1; i < arr.length; i++) {
    //获取当前位置的零时值
    var temp = arr[i];
    //获取当前位置的前一位（即：之前排好序的最后一位）
    int j = i - 1;
    //如果j>=0没有与已排好序的比较晚完 且 零时值小于 j 位的值，则 j 位向后移一位
    while ((j >= 0) && (temp < arr[j])) {
      arr[j + 1] = arr[j];
      //向前移一位
      --j;
    }
    //如果遍历到合适的位置(即：比前一个数字数据大，比后一个数据小),则插入当前空位
    arr[j + 1] = temp;
  }
  //返回排序后的集合
  return arr;
}
复制代码

选择排序

示例图

选择排序

代码实现

///选择排序
List<int> selectionSort(List<int> arr) {
  //数据为空直接返回
  if (arr?.isEmpty ?? true) {
    return arr;
  }
  //循环遍历
  //arr.length - 1 （即：最后一位不与自己比较）
  for (var i = 0; i < arr.length - 1; ++i) {
    //最小值位置
    int minIndex = i;
    //遍历获取最小值位置
    for (var j = i + 1; j < arr.length; ++j) {
      //比较出最小值
      if (arr[j] < arr[minIndex]) {
        //更新最小值位置为当前j的位置
        minIndex = j;
      }
    }
    
    //当前最小值位置不与i位置相等
    if (i != minIndex) {
      //交换位置
      int temp = arr[i];
      arr[i] = arr[minIndex];
      arr[minIndex] = temp;
    }
  }
  //返回排序后的数组
  return arr;
}
复制代码

快速排序

示例图

代码实现

///快速排序
List<int> quickSort(List<int> arr) {
  return _sort(arr, 0, (arr?.length ?? 0) - 1);
}

///排序
List<int> _sort(List<int> arr, int start, int end) {
  //开始位置小于结束位置
  if (start < end) {
    //获取基准值索引
    int pivotIndex = _partition(arr, start, end);
    //排序左边
    _sort(arr, start, pivotIndex - 1);
    //排序右边
    _sort(arr, pivotIndex + 1, end);
  }
  return arr;
}
复制代码


///基准值索引
int _partition(List<int> arr, int lo, int hi) {
  int i = lo, j = hi + 1;
  //获取基准值
  int pivot = arr[lo];
  while (true) {
    //从左往右扫描
    while (arr[++i] < pivot) {
      //遍历到最右边
      if (i == hi) {
        break;
      }
    }
    //从右往左扫描
    while (arr[--j] > pivot) {
      //遍历到最左边
      if (j == lo) {
        break;
      }
    }
    //i与j汇合，说明遍历交换完毕，跳出循环
    if (i >= j) {
      break;
    }

    //交换i和j的位置
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
  //基准值与j位(小于基准值的最后1位**j位本来是大于基准值的第一位，最后一次扫描时--j了)交换位置
  arr[lo] = arr[j];
  arr[j] = pivot;
  return j;
}
复制代码