一定要掌握的常见排序

时间:2020-12-11 14:28:30

一定要熟悉的排序

1.直接插入排序

void InsertSort(int[] a, int n) {
for (int i = 1; i < n; i++) {
if (a[i] < a[i - 1]) { // 若第i个元素大于i-1元素,直接插入。小于的话,移动有序表后插入
int x = a[i]; // 复制为哨兵,即存储待排序元素
int j = 0;
for (j = i - 1; j >= 0; j--) {// 查找在有序表的插入位置
if (x >= a[j]) {
break;
}
a[j
+ 1] = a[j];// 元素后移
}
a[j
+ 1] = x; // 插入到正确位置
}
}
}

2.shell排序

/*
* 设初始序列有n个元素,选定一个小于n大于或等于1的整数gap作为间隔,将全部元素分成子序列,
* 所有距离为gap的元素放在同一个子序列中,在每个子序列中分别采用直接插入算法进行排序;然后缩小间隔gap,如令gap=gap/2,
* 重复上面的子序列划分和子序列排序动作;直到最后gap=1,将所有的元素放到一个序列中为止。
*/
void shellSort(int[] number) {
int gap = number.length / 2; // 一个组合中两个元素的差也是组合类型数

while (gap > 0) {
for (int k = 0; k < gap; k++) {
for (int i = k + gap; i < number.length; i += gap) { // 遍历子序列中的元素,插入排序
for (int j = i - gap; j >= k; j -= gap) {
if (number[j] > number[j + gap]) {
swap(number, j, j
+ gap);
}
else
break;
}
}
}
gap
/= 2;
}
}

void swap(int[] number, int i, int j) {
int t;
t
= number[i];
number[i]
= number[j];
number[j]
= t;
}
3.选择排序
void selectSort(int a[], int n) {
for (int i = 0; i < n; i++) {
int k = i;
for (int j = i + 1; j < n; j++) { // 选择最小的元素
if (a[k] > a[j])
k
= j;
}
if (k != i) {
int tmp = a[i];
a[i]
= a[k];
a[k]
= tmp; // 最小元素与第i位置元素互换
}
}
}

4.冒泡排序

 void bubbleSort(int r[], int n) {
int i = n - 1; // 初始时,最后位置保持不变
while (i > 0) {
int pos = 0; // 每趟开始时,无记录交换
for (int j = 0; j < i; j++)
if (r[j] > r[j + 1]) {
pos
= j; // 记录交换的位置
int tmp = r[j];
r[j]
= r[j + 1];
r[j
+ 1] = tmp;
}
i
= pos; // 为下一趟排序作准备
}
}

5.快速排序

    void quickSort(int R[], int low, int high) {
if (low < high) {
int pos = Partition(R, low, high);
quickSort(R, low, pos
- 1);
quickSort(R, pos
+ 1, high);
}
}

int Partition(int[] r, int i, int j) {
int pivot = r[i];
while (i < j) {
while (i<j && r[j] >= pivot) {
j
--;
}
if (i < j) {
r[i]
= r[j];
i
++;
}
while (i<j && r[i] <= pivot) {
i
++;
}
if (i < j) {
r[j]
= r[i];
j
--;
}
}

r[i]
=pivot;//确定r[pos]的位置
return i;
}