排序算法
1.直接插入排序
（1）將第i個(gè)元素插入到前面的有序數(shù)列中范咨，即從第i-1個(gè)元素開(kāi)始向前遍歷故觅，如果遍歷到的元素大于第i個(gè)元素，則該元素向后移動(dòng)一個(gè)位置渠啊，直至找到一個(gè)不大于第i個(gè)元素的元素或遍歷到arr[0]處输吏，插入第i個(gè)元素。
public static void insertion_sort1(int arr[]) {
int i, j;
for (i = 1; i < arr.length; i++) {
// 獲取第i個(gè)元素
int key = arr[i];
for (j = i - 1; j >= 0; j--) {
// 從第i-1個(gè)元素開(kāi)始向前遍歷
if (arr[j] > key)
arr[j + 1] = arr[j];
else {
break;
}
}
// 找到合適位置替蛉，插入第i個(gè)元素
arr[j + 1] = key;
}
}
（2）將第0個(gè)位置當(dāng)作監(jiān)視哨贯溅，不存放元素
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++) {// 控制每次冒泡的比較次數(shù)
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
flag = 1;
}
}
// 如果一次冒泡沒(méi)有交換元素炼杖，說(shuō)明排序完成
if (flag == 0)
break;
}
}
3.簡(jiǎn)單選擇排序
public static void simple_selection_sort(int arr[]) {
int temp, position;
// 為第i個(gè)位置尋找對(duì)應(yīng)的元素
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.希爾排序
將原序列拆分成多個(gè)子序列，分別對(duì)子序列進(jìn)行直接插入排序盗迟。初始增量為序列長(zhǎng)度的一半，增量最后為1熙含。
public static void shell_sort(int arr[]) {
// 初始增量
int increment = arr.length / 2;
int i, j;
while (increment >= 1) {
// 進(jìn)行插入排序
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) {
// 建最大堆罚缕，依次調(diào)整非葉子結(jié)點(diǎn)的位置
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++) {
// 互換堆頂元素和當(dāng)前最后一個(gè)葉子結(jié)點(diǎn)
int temp = arr[0];
arr[0] = arr[arr.length - 1 - i];
arr[arr.length - 1 - i] = temp;
// 調(diào)整堆頂元素的位置，堆的大小減1
Sift(arr, 0, arr.length - 2 - i);
}
}
// 數(shù)組中第0-high個(gè)元素組成最大堆怎静，調(diào)整第i個(gè)位置上元素的位置
private static void Sift(int[] arr, int i, int high) {
int temp = arr[i];
int j = (2 * i) + 1;// 獲取第i個(gè)位置上對(duì)應(yīng)的左結(jié)點(diǎn)
while (j <= high) {
// 如果有右結(jié)點(diǎn)且右結(jié)點(diǎn)大于左結(jié)點(diǎn)邮弹，獲取第i個(gè)位置上對(duì)應(yīng)的右結(jié)點(diǎn)
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); // 左側(cè)進(jìn)行歸并排序
merge_sort(arr, center + 1, right); // 右側(cè)進(jìn)行歸并排序
merge(arr, left, center + 1, right); // 合并兩個(gè)有序序列
}
}
// 將兩個(gè)有序序列合并為一個(gè)有序序列
private static void merge(int[] arr, int leftPos, int rightPos, int rightEnd) {
int temp[] = new int[arr.length];
int leftEnd = rightPos - 1; // 左側(cè)結(jié)束下標(biāo)
int tempPos = leftPos; // 記錄temp數(shù)組的下標(biāo)
int left = leftPos; // 記錄arr數(shù)組的左側(cè)開(kāi)始下標(biāo)，最后復(fù)制時(shí)需要使用
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) {// 如果左側(cè)還有元素
temp[tempPos] = arr[leftPos];
tempPos++;
leftPos++;
}
while (rightPos <= rightEnd) {// 如果右側(cè)還有元素
temp[tempPos] = arr[rightPos];
tempPos++;
rightPos++;
}
// 將temp數(shù)組中的元素復(fù)制到arr數(shù)組中
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];
// 下面的循環(huán)完成了一趟排序蚓聘，將數(shù)組中小于temp的元素放在左邊腌乡，大于temp的元素放在右邊
while (m != n) {
while (n > m && arr[n] > temp)// 從右往左掃描，找到一個(gè)小于temp的元素
n--;
if (n > m) {// 跳出上方while循環(huán)夜牡，如果n和m不相等与纽，移動(dòng)元素；如果n和m相等塘装，跳出整個(gè)循環(huán)
arr[m] = arr[n];
m++;
}
while (m < n && arr[m] < temp)// 從左往右掃描急迂，找到一個(gè)大于temp的元素
m++;
if (m < n) {// 跳出上方while循環(huán)，如果n和m不相等蹦肴，移動(dòng)元素僚碎；如果n和m相等，跳出整個(gè)循環(huán)
arr[n] = arr[m];
n--;
}
}
arr[m] = temp;// 將temp放到合適的位置上
quick_sort(arr, left, m - 1);
quick_sort(arr, m + 1, right);
}
}
8.基數(shù)排序（桶排序）
從最低位開(kāi)始阴幌，將各個(gè)數(shù)字存儲(chǔ)到對(duì)應(yīng)的桶中勺阐。然后將桶中的元素按照桶的編號(hào)從小到大取出；對(duì)于同一個(gè)桶中的元素矛双，先放入的先取出渊抽，后放入的后取出（保證穩(wěn)定性）。然后循環(huán)進(jìn)行下一位排序议忽，直至最高位排序完成腰吟。
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;
// 計(jì)數(shù)器
int count;
// 排序桶。10代表0-9這10個(gè)數(shù)字徙瓶，arr.length代表一個(gè)桶中最多含有的數(shù)字個(gè)數(shù)
int[][] bucket = new int[10][arr.length];
// 每個(gè)桶的計(jì)數(shù)器毛雇，記錄桶中有多少數(shù)字
int[] order = new int[arr.length];
while (n < d) {
// 將arr數(shù)組中的數(shù)字放入對(duì)應(yīng)的桶中
for (int i = 0; i < arr.length; i++) {
int temp = (arr[i] / n) % 10;// 個(gè)位、十位...的數(shù)據(jù)
bucket[temp][order[temp]] = arr[i];
order[temp]++;
}
count = 0;
for (int i = 0; i < arr.length; i++) {
if (order[i] != 0)// 如果這個(gè)桶中有數(shù)據(jù)侦镇，將這個(gè)桶中的所有數(shù)據(jù)保存到原數(shù)組中
{
for (int j = 0; j < order[i]; j++) {
arr[count] = bucket[i][j];
count++;
}
// 將桶的計(jì)數(shù)器歸0灵疮，用于下一位排序
order[i] = 0;
}
}
n *= 10;
}
}
}
