排序算法
1.直接插入排序
（1）将第i个元素插入到前面的有序数列中，即从第i-1个元素开始向前遍历，如果遍历到的元素大于第i个元素，则该元素向后移动一个位置，直至找到一个不大于第i个元素的元素或遍历到arr[0]处，插入第i个元素。
public static void insertion_sort1(int arr[]) {
int i, j;
for (i = 1; i < arr.length; i++) {
// 获取第i个元素
int key = arr[i];
for (j = i - 1; j >= 0; j--) {
// 从第i-1个元素开始向前遍历
if (arr[j] > key)
arr[j + 1] = arr[j];
else {
break;
}
}
// 找到合适位置，插入第i个元素
arr[j + 1] = key;
}
}
（2）将第0个位置当作监视哨，不存放元素
public static void insertion_sort2(int arr[]) {
int i, j;
for (i = 2; i < arr.length; i++) {
arr[0] = arr[i];
for (j = i - 1; arr[j] > arr[0]; j--) {
arr[j + 1] = arr[j];
}
arr[j + 1] = arr[0];
}
}
2.冒泡排序
public static void bubble_sort(int arr[]) {
int temp, flag;
for (int i = 0; i < arr.length - 1; i++) {// i表示第几次冒泡
flag = 0;
for (int j = 0; j < arr.length - 1 - i; j++) {// 控制每次冒泡的比较次数
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
flag = 1;
}
}
// 如果一次冒泡没有交换元素，说明排序完成
if (flag == 0)
break;
}
}
3.简单选择排序
public static void simple_selection_sort(int arr[]) {
int temp, position;
// 为第i个位置寻找对应的元素
for (int i = 0; i < arr.length - 1; i++) {
position = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[position] > arr[j]) {
position = j;
}
}
if (position != i) {
temp = arr[i];
arr[i] = arr[position];
arr[position] = temp;
}
}
}
4.希尔排序
将原序列拆分成多个子序列，分别对子序列进行直接插入排序。初始增量为序列长度的一半，增量最后为1。
public static void shell_sort(int arr[]) {
// 初始增量
int increment = arr.length / 2;
int i, j;
while (increment >= 1) {
// 进行插入排序
for (i = increment; i < arr.length; i++) {
int key = arr[i];
for (j = i - increment; j >= 0; j = j - increment) {
if (arr[j] > key)
arr[j + increment] = arr[j];
else
break;
}
arr[j + increment] = key;
}
// 下一轮的增量
increment = increment / 2;
}
}
5.堆排序
public static void heap_sort(int[] arr) {
// 建最大堆，依次调整非叶子结点的位置
for (int pos = (arr.length / 2) - 1; pos >= 0; pos--) {
Sift(arr, pos, arr.length - 1);
}
for (int i = 0; i < arr.length - 1; i++) {
// 互换堆顶元素和当前最后一个叶子结点
int temp = arr[0];
arr[0] = arr[arr.length - 1 - i];
arr[arr.length - 1 - i] = temp;
// 调整堆顶元素的位置，堆的大小减1
Sift(arr, 0, arr.length - 2 - i);
}
}
// 数组中第0-high个元素组成最大堆，调整第i个位置上元素的位置
private static void Sift(int[] arr, int i, int high) {
int temp = arr[i];
int j = (2 * i) + 1;// 获取第i个位置上对应的左结点
while (j <= high) {
// 如果有右结点且右结点大于左结点，获取第i个位置上对应的右结点
if (j < high && arr[j] < arr[j + 1])
j++;
if (temp < arr[j]) {
arr[i] = arr[j];
i = j;
j = (2 * i) + 1;
} else {
break;
}
}
arr[i] = temp;
}
6.归并排序
private static void merge_sort(int[] arr, int left, int right) {
if (left < right) {
int center = (left + right) / 2;
merge_sort(arr, left, center); // 左侧进行归并排序
merge_sort(arr, center + 1, right); // 右侧进行归并排序
merge(arr, left, center + 1, right); // 合并两个有序序列
}
}
// 将两个有序序列合并为一个有序序列
private static void merge(int[] arr, int leftPos, int rightPos, int rightEnd) {
int temp[] = new int[arr.length];
int leftEnd = rightPos - 1; // 左侧结束下标
int tempPos = leftPos; // 记录temp数组的下标
int left = leftPos; // 记录arr数组的左侧开始下标，最后复制时需要使用
while (leftPos <= leftEnd && rightPos <= rightEnd) {
if (arr[leftPos] <= arr[rightPos]) {
temp[tempPos] = arr[leftPos];
tempPos++;
leftPos++;
} else {
temp[tempPos] = arr[rightPos];
tempPos++;
rightPos++;
}
}
while (leftPos <= leftEnd) {// 如果左侧还有元素
temp[tempPos] = arr[leftPos];
tempPos++;
leftPos++;
}
while (rightPos <= rightEnd) {// 如果右侧还有元素
temp[tempPos] = arr[rightPos];
tempPos++;
rightPos++;
}
// 将temp数组中的元素复制到arr数组中
for (int i = left; i <= rightEnd; i++) {
arr[i] = temp[i];
}
}
7.快速排序
public static void quick_sort(int arr[], int left, int right) {
int m = left, n = right;
if (left < right) {
int temp = arr[left];
// 下面的循环完成了一趟排序，将数组中小于temp的元素放在左边，大于temp的元素放在右边
while (m != n) {
while (n > m && arr[n] > temp)// 从右往左扫描，找到一个小于temp的元素
n--;
if (n > m) {// 跳出上方while循环，如果n和m不相等，移动元素；如果n和m相等，跳出整个循环
arr[m] = arr[n];
m++;
}
while (m < n && arr[m] < temp)// 从左往右扫描，找到一个大于temp的元素
m++;
if (m < n) {// 跳出上方while循环，如果n和m不相等，移动元素；如果n和m相等，跳出整个循环
arr[n] = arr[m];
n--;
}
}
arr[m] = temp;// 将temp放到合适的位置上
quick_sort(arr, left, m - 1);
quick_sort(arr, m + 1, right);
}
}
8.基数排序（桶排序）
从最低位开始，将各个数字存储到对应的桶中。然后将桶中的元素按照桶的编号从小到大取出；对于同一个桶中的元素，先放入的先取出，后放入的后取出（保证稳定性）。然后循环进行下一位排序，直至最高位排序完成。
public class RadixSort {
public static void main(String[] args) {
int arr[] = new int[] { 73, 122, 93, 43, 555, 14, 828, 65, 39, 81 };
radix_Sort(arr, 1000);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + ",");
}
}
private static void radix_Sort(int[] arr, int d) {
int n = 1;
// 计数器
int count;
// 排序桶。10代表0-9这10个数字，arr.length代表一个桶中最多含有的数字个数
int[][] bucket = new int[10][arr.length];
// 每个桶的计数器，记录桶中有多少数字
int[] order = new int[arr.length];
while (n < d) {
// 将arr数组中的数字放入对应的桶中
for (int i = 0; i < arr.length; i++) {
int temp = (arr[i] / n) % 10;// 个位、十位...的数据
bucket[temp][order[temp]] = arr[i];
order[temp]++;
}
count = 0;
for (int i = 0; i < arr.length; i++) {
if (order[i] != 0)// 如果这个桶中有数据，将这个桶中的所有数据保存到原数组中
{
for (int j = 0; j < order[i]; j++) {
arr[count] = bucket[i][j];
count++;
}
// 将桶的计数器归0，用于下一位排序
order[i] = 0;
}
}
n *= 10;
}
}
}
