我要评论
冒泡排序
思想：对比当前值的下一个值，如果大就交换位置
代码：
/**
* 冒泡排序
*/
public class bubblesort {
public static void main(string[] args) {
int[] array = {1, 5, 3, 2, 4};
bubblesort(array);
system.out.println(arrays.tostring(array));
}
public static void bubblesort(int[] array) {
for (int i = 0; i < array.length; i++) {
for (int j = i + 1; j < array.length; j++) {
if (array[i] > array[j]) {
int temp = array[j];
array[j] = array[i];
array[i] = temp;
}
}
}
}
}
选择排序
思想：选择当前数组中最小的一个值放在起始位置，再从剩下的数组值中选择第二小的值放在前面值的后面，直到选完。
代码：
/**
* 选择排序
*/
public class selectsort {
public static void main(string[] args) {
int[] array = {1, 5, 3, 2, 4};
selectsort(array);
system.out.println(arrays.tostring(array));
}
public static void selectsort(int[] array) {
for (int i = 0; i < array.length; i++) {
int minindex = i;
for (int j = i + 1; j < array.length; j++) {
if (array[minindex] > array[j]) {
minindex = j;
}
}
int temp = array[minindex];
array[minindex] = array[i];
array[i] = temp;
}
}
}
插入排序
思想：
- 首先从第一个元素开始，该元素被认为是有序的；
- 取出下一个元素，在已经排序的元素序列中从后往前进行扫描；
- 如果该已排好序的元素大于新元素，则将该元素移到下一位置；
- 重复步骤3一直往前进行扫描比较，直到找到已排序的元素小于或者等于新元素的位置；
- 将新元素插入到该位置后；
- 重复步骤2~5。
代码：
public class insertsort {
public static void main(string[] args) {
int[] array = {1, 5, 3, 2, 4};
insertsort(array);
system.out.println(arrays.tostring(array));
}
public static void insertsort(int[] a) {
for (int i = 1; i < a.length; i++) {
int j = i - 1;
int current = a[i];
while (a[j] > current && j > 0) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = current;
}
}
}
希尔排序
思想：更加高效的排序，是插入排序的升级版，总的来说就是先分组做插入排序，最后当gap为1时，再对整个数组进行一次插入排序，这时候数组基本有序，所以最后一次插入排序耗时很低。
代码：
public class shellsort {
public static void main(string[] args) {
int[] array = {1, 5, 3, 2, 4};
shellsort(array);
system.out.println(arrays.tostring(array));
}
public static void shellsort(int[] a) {
int len = a.length;
int temp;
int j;
for (int gap = len / 2; gap >= 1; gap = gap / 2) {
for (int i = gap; i < len; i++) {
temp = a[i];
j = i - gap;
while (j > 0 && a[j] > temp) {
a[j + gap] = a[j];
j -= gap;
}
a[j + gap] = temp;
}
}
}
}
快速排序
思想： 选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。
public class quicksort {
public static void main(string[] args) {
int[] arr = {10, 7, 8, 9, 1, 5};
quicksort(arr, 0, arr.length - 1);
system.out.println(arrays.tostring(arr));
}
public static void quicksort(int[] arr, int low, int high) {
if (low < high) {
// pi 是分区索引，arr[p] 现在已经到位
int pi = partition(arr, low, high);
// 分别对 pi 左边和右边的子数组进行递归排序
quicksort(arr, low, pi - 1);
quicksort(arr, pi + 1, high);
}
}
// 这个函数将数组分为两部分，并返回分区索引
public static int partition(int[] arr, int low, int high) {
int pivot = arr[high]; // 选择最右边的元素作为主元
int i = (low - 1); // 指向最小元素的指针
for (int j = low; j <= high - 1; j++) {
// 如果当前元素小于或等于主元
if (arr[j] <= pivot) {
i++;
// 交换 arr[i] 和 arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 交换 arr[i+1] 和 arr[high] (或主元)
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
}
归并排序
思想：采用分治法，从中间拆分为2个子组，然后递归拆分子组直到每个子组数量为1，不断的将相邻两个子组合并并且排序直到只剩一个组
代码：
public class mergesorttest {
public static void main(string[] args) {
int[] array = {1, 5, 3, 2, 4};
mergesort(array);
system.out.println(arrays.tostring(array));
}
public static void mergesort(int[] array) {
if (array == null || array.length == 1) {
return;
}
mergesort(array, 0, array.length - 1);
}
public static void mergesort(int[] array, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
// 对左半部分进行归并排序
mergesort(array, left, mid);
// 对右半部分进行归并排序
mergesort(array, mid + 1, right);
// 合并两个有序数组
merge(array, left, mid, right);
}
}
//合并左右两侧子数组
public static void merge(int[] array, int left, int mid, int right) {
//临时数组
int[] temp = new int[right - left + 1];
//左边指针
int p1 = left;
//右侧指针
int p2 = mid + 1;
//临时数组下标
int tempindex = 0;
//此步就是合并左右两边，然后比大小，排序
while (p1 <= mid && p2 <= right) {
temp[tempindex++] = array[p1] < array[p2] ? array[p1++] : array[p2++];
}
while (p1 <= mid) {
temp[tempindex++] = array[p1++];
}
while (p2 <= right) {
temp[tempindex++] = array[p2++];
}
//将临时数组的元素复制回原数组
if (tempindex >= 0) system.arraycopy(temp, 0, array, left, tempindex);
}
}
堆排序
思想：
堆排序是一种基于二叉堆（通常是大顶堆或小顶堆）的比较排序算法。其基本思想是将待排序的序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个序列重新构造成一个堆，这样会得到n个元素中的次大值。 如此反复执行，便能得到一个有序序列了。
代码：
public class heapsort {
public static void main(string[] args) {
int[] arr = {10, 7, 8, 9, 1, 5, 3, 5, 5, 2, 0, 6, 0, 9};
sort(arr);
system.out.println(arrays.tostring(arr));
}
public static void sort(int arr[]) {
int n = arr.length;
// 构建最大堆(从最后一个非叶子节点开始)
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// 一个一个从堆顶取出元素，将堆顶元素沉到数组末端
for (int i = n - 1; i >= 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// 重新调整堆
heapify(arr, i, 0);
}
}
// 调整堆
/**
* 调整堆
* 关键解释：
* 大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
* 小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
*/
static void heapify(int arr[], int n, int i) {
int largest = i; // 初始化最大值为根
int left = 2 * i + 1; // 左 = 2*i + 1
int right = 2 * i + 2; // 右 = 2*i + 2
// 如果左子节点大于根
if (left < n && arr[left] > arr[largest])
largest = left;
// 如果右子节点大于目前已知的最大值
if (right < n && arr[right] > arr[largest])
largest = right;
// 如果最大值不是根
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// 递归调整受影响的子堆
heapify(arr, n, largest);
}
}
}
发表评论