01-排序算法

nobility 发布于 2020-04-23 2256 次阅读

排序算法

冒泡排序

JavaScript版

var sortArray = function (nums) {
  let flag = true;
  for (let i = 0; i < nums.length - 1; i++) {
    for (let j = 0; j < nums.length - i - 1; j++) {
      if (nums[j] > nums[j + 1]) {
        swap(nums, j, j + 1);
        flag = false;
      }
    }
    if (flag) {
      break;
    }
  }
  return nums;
};

var swap = function (arr, a, b) {
  let temp = arr[a];
  arr[a] = arr[b];
  arr[b] = temp;
};

Java版

class Solution {
  public int[] sortArray(int[] nums) {
    boolean flag = true;
		for (int i = 0; i < nums.length - 1; i++) {
      for (int j = 0; j < nums.length - i - 1; j++) {
        if (nums[j] > nums[j + 1]) {
          swap(nums, j, j+1);
          flag = false;
        }
      }
      if (flag) {
        black;
      }
    }
    return nums;
  }
  public void swap(int[] arr, int a, int b) {
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
  }
}

选择排序

JavaScript版

var sortArray = function (nums) {
  for (let i = 0; i < nums.length - 1; i++) {
    let minIndex = i;
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[j] < nums[minIndex]) {
        minIndex = j;
      }
    }
    swap(nums, i, minIndex);
  }
  return nums;
};

var swap = function (arr, a, b) {
  let temp = arr[a];
  arr[a] = arr[b];
  arr[b] = temp;
};

Java版

class Solution {
  public int[] sortArray(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
      int minIndex = i;
      for (int j = i + 1; j < nums.length; j++) {
        if (nums[j] < nums[minIndex]) {
          minIndex = j;
        }
      }
      swap(nums, i, minIndex);
    }
    return nums;
  }
  public void swap (int[] arr, int a, int b) {
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
  }
}

插入排序

JavaScript版

var sortArray = function (nums) {
  for (let i = 1; i < nums.length; i++) {
    let element = nums[i];
    let j;
    for (j = i; j > 0; j--) {
      if (nums[j - 1] > element) {
        nums[j] = nums[j - 1];
      } else {
        break;
      }
    }
    nums[j] = element;
  }
  return nums;
};

Java版

class Solution {
  public int[] sortArray(int[] nums) {
    for (int i = 1; i < nums.length; i++) {
      int element = nums[i];
      int j;
      for (j = i; j > 0; j--) {
        if (nums[j - 1] > element) {
          nums[j] = nums[j - 1];
        } else {
          break;
        }
      }
      nums[j] = element;
    }
    return nums;
  }
}

归并排序

递归方式

JavaScript版
var sortArray = function (nums) {
  mergeSort(nums, 0, nums.length - 1);
  return nums;
};
var mergeSort = function (arr, left, right) {
  if (left >= right) {
    return;
  }
  let middle = Math.trunc((left + right) / 2);
  mergeSort(arr, left, middle);
  mergeSort(arr, middle + 1, right);
  if (arr[middle] > arr[middle + 1]) {
    merge(arr, left, middle, right);
  }
};
var merge = function(arr, left, middle, right) {
  let temp = new Array(right - left + 1);
  for (let i = left; i <= right; i++) {
    temp[i - left] = arr[i];
  }
  let leftIndex = left, rightIndex =  middle + 1;
  for (let i = left; i <= right; i++) {
    if(leftIndex > middle) {
      arr[i] = temp[rightIndex - left];
      rightIndex++;
    } else if (rightIndex > right) {
      arr[i] = temp[leftIndex - left];
      leftIndex++;
    } else if (temp[leftIndex - left] < temp[rightIndex - left]) {
      arr[i] = temp[leftIndex - left];
      leftIndex++;
    } else {
      arr[i] = temp[rightIndex - left];
      rightIndex++;
    }
  }
};
Java版
class Solution {
  public int[] sortArray(int[] nums) {
    mergeSort(nums, 0, nums.length - 1);
    return nums;
  }
  public void mergeSort(int[] arr, int left, int right) {
    if (left >= right) {
      return;
    }
    int middle = (left + right) / 2;
    mergeSort(arr, left, middle);
    mergeSort(arr, middle + 1, right);
    if (arr[middle] > arr[middle + 1]) {
      merge(arr, left, middle, right);
    }
  }
  public void merge(int[] arr, int left, int middle, int right) {
    int[] temp = new int[right - left + 1];
    for (int i = left; i <= right; i++) {
      temp[i - left] = arr[i];
    }
    int leftIndex = left, rightIndex = middle + 1;
    for (int i = left; i <= right; i++) {
      if (leftIndex > middle) {
        arr[i] = temp[rightIndex - left];
        rightIndex++;
      } else if (rightIndex > right) {
        arr[i] = temp[leftIndex - left];
        leftIndex++;
      } else if (temp[leftIndex - left] < temp[rightIndex - left]) {
        arr[i] = temp[leftIndex - left];
        leftIndex++;
      } else {
        arr[i] = temp[rightIndex - left];
        rightIndex++;
      }
    }
  }
}

非递归方式

JavaScript版
var sortArray = function (nums) {
  for (let i = 1; i <= nums.length; i += i) {
    for (let j = 0; j + i < nums.length; j += i + i) {
      if(nums[j + i - 1] > nums[j + i]) {
        merge(nums, j, j + i - 1, Math.min(j + i + i - 1, nums.length - 1));
      }
    }
  }
  return nums;
};
var merge = function(arr, left, middle, right) {
  let temp = new Array(right - left + 1);
  for (let i = left; i <= right; i++) {
    temp[i - left] = arr[i];
  }
  let leftIndex = left, rightIndex =  middle + 1;
  for (let i = left; i <= right; i++) {
    if(leftIndex > middle) {
      arr[i] = temp[rightIndex - left];
      rightIndex++;
    } else if (rightIndex > right) {
      arr[i] = temp[leftIndex - left];
      leftIndex++;
    } else if (temp[leftIndex - left] < temp[rightIndex - left]) {
      arr[i] = temp[leftIndex - left];
      leftIndex++;
    } else {
      arr[i] = temp[rightIndex - left];
      rightIndex++;
    }
  }
};
Java版
class Solution {
  public int[] sortArray(int[] nums) {
    for (int i = 1; i <= nums.length; i += i) {
      for (int j = 0; j + i < nums.length; j += i + i) {
        if(nums[j + i - 1] > nums[j + i]) {
          merge(nums, j, j + i - 1, Math.min(j + i + i - 1, nums.length - 1));
        }
      }
  	}
    return nums;
  }
  public void merge(int[] arr, int left, int middle, int right) {
    int[] temp = new int[right - left + 1];
    for (int i = left; i <= right; i++) {
      temp[i - left] = arr[i];
    }
    int leftIndex = left, rightIndex = middle + 1;
    for (int i = left; i <= right; i++) {
      if (leftIndex > middle) {
        arr[i] = temp[rightIndex - left];
        rightIndex++;
      } else if (rightIndex > right) {
        arr[i] = temp[leftIndex - left];
        leftIndex++;
      } else if (temp[leftIndex - left] < temp[rightIndex - left]) {
        arr[i] = temp[leftIndex - left];
        leftIndex++;
      } else {
        arr[i] = temp[rightIndex - left];
        rightIndex++;
      }
    }
  }
}

快速排序

随机快排

JavaScript版
var sortArray = function (nums) {
  quickSort(nums, 0, nums.length - 1);
  return nums;
};
var quickSort = function (arr, left, right) {
  if (left >= right) {
    return;
  }
  let p = partition(arr, left, right);
  quickSort(arr, left, p - 1);
  quickSort(arr, p + 1, right);
};
var partition = function (arr, left, right) {
  let randomIndex = parseInt(Math.random() * (right - left + 1) + left, 10);
  swap(arr, left, randomIndex);
  
  let baseElement = arr[left];
  let middleIndex = left;
  for (let i = left + 1; i <= right; i++) {
    if (arr[i] < baseElement) {
      swap(arr, middleIndex + 1, i);
      middleIndex++;
    }
  }
  swap(arr, left, middleIndex);
  return middleIndex;
};
var swap = function (arr, a, b) {
  let temp = arr[a];
  arr[a] = arr[b];
  arr[b] = temp;
};
Java版
class Solution {
  public int[] sortArray(int[] nums) {
    quickSort(nums, 0, nums.length - 1);
    return nums;
  }
  public void quickSort(int[] arr, int left, int right) {
    if (left >= right) {
    	return;
  	}
    int p = partition(arr, left, right);
    quickSort(arr, left, p - 1);
    quickSort(arr, p + 1, right);
  }
  public int partition(int[] arr, int left, int right) {
    int randomIndex = (int) Math.random() * (right - left + 1) + left;
  	swap(arr, left, randomIndex);
    
    int baseElement = arr[left];
    int middleIndex = left;
    for (int i = left + 1; i <= right; i++) {
      if (arr[i] < baseElement) {
        swap(arr, middleIndex + 1, i);
        middleIndex++;
      }
    }
    swap(arr, left, middleIndex);
    return middleIndex;
  }
  public void swap(int[] arr, int a, int b) {
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
  }
}

双路快排

JavaScript版
var sortArray = function (nums) {
  quickSort(nums, 0, nums.length - 1);
  return nums;
};
var quickSort = function (arr, left, right) {
  if (left >= right) {
    return;
  }
  let p = partition(arr, left, right);
  quickSort(arr, left, p - 1);
  quickSort(arr, p + 1, right);
};
var partition = function (arr, left, right) {
  let randomIndex = parseInt(Math.random() * (right - left + 1) + left, 10);
  swap(arr, left, randomIndex);
  
  let baseElement = arr[left];
  let leftIndex = left + 1, rightIndex = right;
  while (true) {
    while (leftIndex <= right && arr[leftIndex] < baseElement) leftIndex++;
    while (rightIndex >= left + 1 && arr[rightIndex] > baseElement) rightIndex--;
    if (leftIndex > rightIndex) {
      break;
    }
    swap(arr, leftIndex, rightIndex);
    leftIndex++;
    rightIndex--;
  }
  swap(arr, left, rightIndex);
  return rightIndex;
};
var swap = function (arr, a, b) {
  let temp = arr[a];
  arr[a] = arr[b];
  arr[b] = temp;
};
Java版
class Solution {
  public int[] sortArray(int[] nums) {
    quickSort(nums, 0, nums.length - 1);
    return nums;
  }
  public void quickSort(int[] arr, int left, int right) {
    if (left >= right) {
    	return;
  	}
    int p = partition(arr, left, right);
    quickSort(arr, left, p - 1);
    quickSort(arr, p + 1, right);
  }
  public int partition(int[] arr, int left, int right) {
    int randomIndex = (int) Math.random() * (right - left + 1) + left;
  	swap(arr, left, randomIndex);
    
    int baseElement = arr[left];
    int leftIndex = left + 1, rightIndex = right;
    while (true) {
      while (leftIndex <= right && arr[leftIndex] < baseElement) leftIndex++;
      while (rightIndex >= left + 1 && arr[rightIndex] > baseElement) rightIndex--;
      if (leftIndex > rightIndex) {
        break;
      }
      swap(arr, leftIndex, rightIndex);
      leftIndex++;
      rightIndex--;
    }
    swap(arr, left, rightIndex);
  	return rightIndex;
  }
  public void swap(int[] arr, int a, int b) {
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
  }
}

三路快排

JavaScript版
var sortArray = function (nums) {
  quickSort(nums, 0, nums.length - 1);
  return nums;
};
var quickSort = function (arr, left, right) {
  if (left >= right) {
    return;
  }
  let [leftIndex, rightIndex] = partition(arr, left, right);
  quickSort(arr, left, leftIndex - 1);
  quickSort(arr, rightIndex, right);
};
var partition = function (arr, left, right) {
  let randomIndex = parseInt(Math.random() * (right - left + 1) + left, 10);
  swap(arr, left, randomIndex);
  
  let baseElement = arr[left];
  let leftIndex = left, rightIndex = right + 1;
  let i = left + 1;
  while (i < rightIndex) {
    if (arr[i] < baseElement) {
      swap(arr, i, leftIndex + 1);
      leftIndex++;
      i++;
    } else if (arr[i] > baseElement) {
      swap(arr, i, rightIndex - 1);
      rightIndex--;
    } else {
      i++;
    }
  }
  swap(arr, left, leftIndex);
  return [leftIndex, rightIndex];
};
var swap = function (arr, a, b) {
  let temp = arr[a];
  arr[a] = arr[b];
  arr[b] = temp;
};
Java版
class Solution {
  public int[] sortArray(int[] nums) {
    quickSort(nums, 0, nums.length - 1);
    return nums;
  }
  public void quickSort(int[] arr, int left, int right) {
    if (left >= right) {
    	return;
  	}
    int[] result = partition(arr, left, right);
    int leftIndex = result[0];
    int rightIndex = result[1];
    quickSort(arr, left, leftIndex - 1);
    quickSort(arr, rightIndex, right);
  }
  public int[] partition(int[] arr, int left, int right) {
    int randomIndex = (int) Math.random() * (right - left + 1) + left;
  	swap(arr, left, randomIndex);
    
    int baseElement = arr[left];
    int leftIndex = left, rightIndex = right + 1;
    int i = left + 1;
    while (i < rightIndex) {
      if (arr[i] < baseElement) {
        swap(arr, i, leftIndex + 1);
        leftIndex++;
        i++;
      } else if (arr[i] > baseElement) {
        swap(arr, i, rightIndex - 1);
        rightIndex--;
      } else {
        i++;
      }
    }
    swap(arr, left, leftIndex);
    return new int[] {leftIndex, rightIndex};
  }
  public void swap(int[] arr, int a, int b) {
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
  }
}

堆排序

JavaScript版

var sortArray = function (nums) {
  for (let i = Math.trunc((nums.length - 1) / 2); i >= 0; i--) {
    shiftDown(nums, nums.length, i);
  }
  for (let i = nums.length - 1; i > 0; i--) {
    swap(nums, 0, i);
    shiftDown(nums, i, 0);
  }
  return nums;
};
var shiftDown = function (arr, count, index) {
  while (2 * index + 1 < count) {
    let maxIndex = 2 * index + 1;
    if (maxIndex + 1 < count && arr[maxIndex + 1] > arr[maxIndex]) {
      maxIndex += 1; 
    }
    if (arr[index] > arr[maxIndex]) {
      break;
    }
    swap(arr, index, maxIndex);
    index = maxIndex;
  }
};
var swap = function (arr, a, b) {
  let temp = arr[a];
  arr[a] = arr[b];
  arr[b] = temp;
};

Java版

class Solution {
  public int[] sortArray(int[] nums) {
    for (int i = (nums.length - 1) / 2; i >= 0; i--) {
      shiftDown(nums, nums.length, i);
    }
    for (int i = nums.length - 1; i >= 0; i--) {
      swap(nums, 0, i);
      shiftDown(nums, i, 0);
    }
    return nums;
  }
  public void shiftDown(int[] arr, int count, int index) {
    while (2 * index + 1 < count) {
      int maxIndex = 2 * index + 1;
      if (maxIndex + 1 < count && arr[maxIndex + 1] > arr[maxIndex]) {
        maxIndex += 1;
      }
      if (arr[index] > arr[maxIndex]) {
        break;
      }
      swap(arr, index, maxIndex);
      index = maxIndex;
    }
  }
  public void swap(int[] arr, int a, int b) {
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
  }
}
此作者没有提供个人介绍
最后更新于 2020-04-23
啥也没有呀