六大排序算法及Java实现

程序员文章站 2024-03-16 11:55:34

...

冒泡排序

基本思想：

冒泡排序，类似于水中冒泡，较大的数沉下去，较小的数慢慢冒起来，假设从小到大，即为较大的数慢慢往后排，较小的数慢慢往前排。

算法平均时间复杂度为O(n^2)，且较为稳定

六大排序算法及Java实现

代码实现

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BubbleSort {
  public static int[] Data = new int[20];   // 数据数组

  public static void main(String[] args) {

    int Index;   // 数组下标变量

    System.out.println("Input the values(Exit for 0):");

    Index = 0;

    InputStreamReader is = new InputStreamReader(System.in);
    BufferedReader br = new BufferedReader(is);
    StringTokenizer st;

    do {
      System.out.print("Data:" + Index + ":");
      try {
        String myLine = br.readLine();
        st = new StringTokenizer(myLine);
        Data[Index] = Integer.parseInt(st.nextToken());
      } catch (IOException ioe) {
        System.out.print("IO Error:" + ioe);
      }
      Index++;
    } while (Data[Index - 1] != 0);

    Index--;

    System.out.println("Index:" + Index);
    printArray(Data, Index);

    bubblesort(Index);

    System.out.println("");
    printArray(Data, Index);
  }

  public static void printArray(int[] array, int Index) {
    for (int i = 0; i < Index; i++) {
      System.out.print(array[i] + " ");
    }
    System.out.println("");
  }

  public static void bubblesort(int Index) {
    for (int i = 0; i < Index - 1; i ++) {
      for (int j = i + 1; j < Index; j ++) {
        if (Data[i] > Data[j]) {
          swap(Data, i, j);
        }
      }
    }
  }

  private static void swap(int[] array, int ind1, int ind2) {
    int temp = array[ind1];
    array[ind1] = array[ind2];
    array[ind2] = temp;
  }
}

选择排序

主要目标：

每次遍历找到剩余数组中最小的元素

中心思想：

1.第一个循环初始化最小值和最小值索引

2.在第一个循环内部再进行一次循环，对数组元素遍历比较，交换最小值及其索引

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class SelectSort {
  public static int[] Data = new int[20];   // 数据数组

  public static void main(String[] args) {

    int Index;   // 数组下标变量

    System.out.println("Input the values(Exit for 0):");

    Index = 0;

    InputStreamReader is = new InputStreamReader(System.in);
    BufferedReader br = new BufferedReader(is);
    StringTokenizer st;

    do {
      System.out.print("Data:" + Index + ":");
      try {
        String myLine = br.readLine();
        st = new StringTokenizer(myLine);
        Data[Index] = Integer.parseInt(st.nextToken());
      } catch (IOException ioe) {
        System.out.print("IO Error:" + ioe);
      }
      Index++;
    } while (Data[Index - 1] != 0);

    Index--;

    System.out.println("Index:" + Index);
    printArray(Data, Index);

    selectsort(Index);

    System.out.println("");
    printArray(Data, Index);
  }

  public static void printArray(int[] array, int Index) {
    for (int i = 0; i < Index; i++) {
      System.out.print(array[i] + " ");
    }
    System.out.println("");
  }

  public static void selectsort(int Index) {
    int min = 32767;
    int minIndex = 0;

    for(int i = 0; i < Index - 1; i++) {
      min = 32767;
      minIndex = i;
      for (int j =i;j < Index; j++) {
        if (min > Data[j]) {
          min = Data[j];
          minIndex = j;
        }
      }
      swap(Data, minIndex, i);
    }
  }

  private static void swap(int[] array, int ind1, int ind2) {

    int temp = array[ind1];
    array[ind1] = array[ind2];
    array[ind2] = temp;
  }

}

插入排序

插入排序是一种简单直观而且稳定的排序算法，时间复杂度O(n^2 )，若列表初始排序为正序，则时间复杂度为O(n)，反序或无序均为O(n^2 )

插入排序对几乎已经排好序的数据操作时，效率很高

1 基本思想

将数组的第一个数认为是有序数组，从后往前（从前往后）扫描该有序数组，把数组中其余n-1个数，根据数值的大小，插入到有序数组中，直至数组中的所有数有序排列为止。这样的话，n个元素需要进行n-1趟排序！！！

六大排序算法及Java实现

Java代码实现

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;

public class insertsort {
  public static int[] Data = new int[10];   // 数据数组

  public static void main(String[] args) {

    int i;   // 循环变量
    int Index;   // 数组下标变量

    System.out.println("Input the values(Exit for 0):");

    Index = 0;

    Scanner input = new Scanner(System.in);

    InputStreamReader is = new InputStreamReader(System.in);
    BufferedReader br = new BufferedReader(is);
    StringTokenizer st;

    do {
      System.out.print("Data:" + Index + ":");
      try {
        String myLine = br.readLine();
        st = new StringTokenizer(myLine);
        Data[Index] = Integer.parseInt(st.nextToken());
      } catch (IOException ioe) {
        System.out.print("IO Error:" + ioe);
      }
      Index++;
    } while (Data[Index - 1] != 0);

    Index--;

    System.out.println("Index:" + Index);
    printArray(Data, Index);

    InsertSort(Index);

    System.out.println("");
    printArray(Data, Index);
  }

  public static void printArray(int[] array, int Index) {
    for (int i = 0; i < Index; i++) {
      System.out.print(array[i] + " ");
    }
    System.out.println("");
  }

  public static void InsertSort(int Index) {
    int i, j, l;
    int InsertNode;   // 哨兵

    for (i = 1; i < Index; i++) {
      InsertNode = Data[i];

      System.out.println("\n---开始寻找哨兵---");
      j = i - 1;
      while (j >= 0 && Data[j] > InsertNode) {
        Data[j + 1] = Data[j];
        j--;
        printArray(Data, Index);
      }
      System.out.println("---开始插入哨兵---");
      Data[j + 1] = InsertNode;
      printArray(Data, Index);
    }
  }
}

堆排序

堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最好、最坏、平均时间复杂度均为O(nlogn)，它也是不稳定排序。

堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：

六大排序算法及Java实现

基本思想

将排序序列构造成一个大(小)顶堆，此时整个序列的最大值就是堆顶的根节点。将末尾元素进行交换，此时末尾就为最大值。然后将剩余元素重新构造堆，反复执行。

步骤一： 构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。

步骤二： 将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。

不错的博客讲解

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


public class HeapSort {
  public static int[] Data = new int[20];   // 数据数组

  public static void main(String[] args) {

    int Index = 0;   // 数组下标变量

    System.out.println("Input the values(Exit for 0):");

    InputStreamReader is = new InputStreamReader(System.in);
    BufferedReader br = new BufferedReader(is);
    StringTokenizer st;

    do {
      System.out.print("Data:" + Index + ":");
      try {
        String myLine = br.readLine();
        st = new StringTokenizer(myLine);
        Data[Index] = Integer.parseInt(st.nextToken());
      } catch (IOException ioe) {
        System.out.print("IO Error:" + ioe);
      }
      Index++;
    } while (Data[Index - 1] != 0);

    Index--;

    System.out.println("Index:" + Index);
    printArray(Data, Index);

    heapsort(Index);

    System.out.println("");
    printArray(Data, Index);
  }

  public static void printArray(int[] array, int Index) {
    for (int i = 0; i < Index; i++) {
      System.out.print(array[i] + " ");
    }
    System.out.println("");
  }

  /**
   * 将数组排列为大顶堆
   *
   * @param arr    数组
   * @param ind    根节点
   * @param length 数组长度
   */
  public static void adjustHeap(int[] arr, int ind, int length) {

    int temp = arr[ind];

    for(int i = ind * 2 + 1; i < length; i = 2 * i + 1) {

      if (i + 1 < length && arr[i] < arr[i + 1]) {
        i++;
      }

      if (arr[i] > temp) {
        arr[ind] = arr[i];
        ind = i;
      } else {
        break;
      }
    }
    arr[ind] = temp;
  }

  public static void heapsort(int Index) {

    // 构建大顶堆
    for (int i = Index / 2 - 1; i >= 0; i--) {
      adjustHeap(Data, i, Index);
    }

    for (int j = Index - 1; j > 0; j--) {
      swap(Data, 0, j);   // 将堆顶元素与末尾元素进行交换
      adjustHeap(Data, 0, j);   //重新对堆进行调整
    }
  }

  private static void swap(int[] array, int ind1, int ind2) {

    int temp = array[ind1];
    array[ind1] = array[ind2];
    array[ind2] = temp;
  }
}

希尔排序

希尔排序也是插入排序的一种，它是经过改进之后的一个更高效的版本。

基本思想：

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

六大排序算法及Java实现

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class ShellSort {
  public static int[] Data = new int[20];   // 数据数组

  public static void main(String[] args) {

    int Index;   // 数组下标变量

    System.out.println("Input the values(Exit for 0):");

    Index = 0;

    InputStreamReader is = new InputStreamReader(System.in);
    BufferedReader br = new BufferedReader(is);
    StringTokenizer st;

    do {
      System.out.print("Data:" + Index + ":");
      try {
        String myLine = br.readLine();
        st = new StringTokenizer(myLine);
        Data[Index] = Integer.parseInt(st.nextToken());
      } catch (IOException ioe) {
        System.out.print("IO Error:" + ioe);
      }
      Index++;
    } while (Data[Index - 1] != 0);

    Index--;

    System.out.println("Index:" + Index);
    printArray(Data, Index);

    shellsort(Index);

    System.out.println("");
    printArray(Data, Index);
  }

  public static void printArray(int[] array, int Index) {
    for (int i = 0; i < Index; i++) {
      System.out.print(array[i] + " ");
    }
    System.out.println("");
  }

  public static void shellsort(int Index) {
    int temp;

    for (int gap = Index/2; gap > 1; gap /= 2) {

      // 插入排序
      System.out.println("---插入排序gap:" + gap + " ---");
      for(int i = gap; i < Index; i++) {
        System.out.println("i:" + i);
        int j = i;

        while (j - gap >= 0 && Data[j] < Data[j - gap]) {
          System.out.println("j:" + j);

          temp = Data[j];
          Data[j] = Data[j - gap];
          Data[j - gap] = temp;

          printArray(Data, Index);

          j -= gap;
        }

      }
      System.out.println("");
    }
  }
}

快速排序

主要目标：

找到每个数组元素正确的索引值

中心思想：

将数组第一个元素设为基准元素
设两个变量哨兵i 和哨兵j，先从j开始，使其从最后一位索引开始递减（j必须大于等于i），直至找到小于基准元素的值，暂停
哨兵i从第一位索引开始递增（i必须小于等于j），直至找到大于基准元素的值，暂停，若i!= j，则交换 i 和 j 所在位置的数组元素
若 i==j ，则交换基准元素和i所在位置的数组元素，并且此时根据索引i 将数组分为前后两部分，将这两个数组进行递归操作。

这篇博客讲的还不错通俗易懂

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class QuickSort {
  public static int[] Data = new int[20];   // 数据数组

  public static void main(String[] args) {

    int Index;   // 数组下标变量

    System.out.println("Input the values(Exit for 0):");

    Index = 0;

    InputStreamReader is = new InputStreamReader(System.in);
    BufferedReader br = new BufferedReader(is);
    StringTokenizer st;

    do {
      System.out.print("Data:" + Index + ":");
      try {
        String myLine = br.readLine();
        st = new StringTokenizer(myLine);
        Data[Index] = Integer.parseInt(st.nextToken());
      } catch (IOException ioe) {
        System.out.print("IO Error:" + ioe);
      }
      Index++;
    } while (Data[Index - 1] != 0);

    Index--;

    System.out.println("Index:" + Index);
    printArray(Data, Index);

    quicksort(0, Index - 1);

    System.out.println("");
    printArray(Data, Index);
  }

  public static void printArray(int[] array, int Index) {
    for (int i = 0; i < Index; i++) {
      System.out.print(array[i] + " ");
    }
    System.out.println("");
  }

  public static void quicksort(int left, int right) {
    int i = left, j = right;
    int base = Data[left];

//    System.out.print("\n===该数组为");
//    for (int k = left; k <= right; k ++) {
//      System.out.print(" " + Data[k]);
//    }
//    System.out.println(" ===\n");

    while (i < j) {
      while (Data[j] >= base && j > i) {
        j--;
      }

      while (Data[i] <= base && i < j) {
        i++;
      }

      if (i == j) {
        swap(Data, left, i);
//        System.out.println("\n---改变哨兵---");
//        printArray(Data, Data.length);
        quicksort(left, i - 1);
        quicksort(i + 1, right);
        break;
      } else {
        swap(Data, i, j);
//        System.out.printf("\n---交换哨兵i: %d j: %d---\n", i, j);
//        printArray(Data, Data.length);
      }
    }
  }

  private static void swap(int[] array, int ind1, int ind2) {

    int temp = array[ind1];
    array[ind1] = array[ind2];
    array[ind2] = temp;
  }
}

相关标签：数据结构与算法算法数据结构

上一篇： 711问题-优化蛮力求解

下一篇：六大排序算法的总结

六大排序算法及Java实现

冒泡排序

基本思想：

代码实现

选择排序

主要目标：

中心思想：

插入排序

1 基本思想

Java代码实现

堆排序

基本思想

希尔排序

基本思想：

快速排序

主要目标：

中心思想：

Java 排序算法之计数排序

六大排序算法及Java实现

六大排序算法比较

六大排序算法的总结

Java实现基数排序

基数排序实现（java）

动图演示 | C++实现六大排序算法

Java归并排序的实现

排序算法--堆排序（java）

【Java学习笔记】排序算法：冒泡排序、快速排序、选择排序、插入排序算法思想及其Java代码实现