一、直接插入排序
int[] insertSort(int[] arr) {
int temp, i, j;
int n = arr.length;
for (i = 1; i < n; i++) {
temp = arr[i];//从第二个元素开始,与前面的元素比较,如果比前面的大,就不用动,
// 小则将前面的放到temp的位置,temp继续与前面的比较
j = i - 1;
while (j >= 0 && temp < arr[j]) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp;
}
return arr;
}
排序过程:整个排序过程为n-1趟插入,即先将序列中第1个记录看成是一个有序子序列,然后从第2个记录开始,逐个进行插入,直至整个序列有序。
二、希尔排序
int[] shellSort(int[] arr) {
int i, j, n, gap, temp;
n = arr.length;
for (gap = n / 2; gap > 0; gap /= 2) {
for (i = gap; i < n; i++) { //-----------------+-----------+
temp = arr[i]; // |
for (j = i; j >= gap && temp < arr[j - gap]; j -= gap) { // | 此范围
arr[j] = arr[j - gap]; // | 相当于
} // | 插入排序
arr[j] = temp; // |
} //-------------------------------------------------+-----------+
}
return arr;
}
排序过程:先取一个正整数d1 三、简单选择排序 排序过程 :首先通过n-1次关键字比较,从n个记录中找出关键字最小的记录,将它与第一个记录交换 再通过n-2次比较,从剩余的n-1个记录中找出关键字次小的记录,将它与第二个记录交换 重复上述操作,共进行n-1趟排序后,排序结束 四、堆排序 五、冒泡排序 排序过程: 将第一个记录的关键字与第二个记录的关键字进行比较,若为逆序r[1].key>r[2].key,则交换;然后比较第二个记录与第三个记录;依次类推,直至第n-1个记录和第n个记录比较为止——第一趟冒泡排序,结果关键字最大的记录被安置在最后一个记录上 对前n-1个记录进行第二趟冒泡排序,结果使关键字次大的记录被安置在第n-1个记录位置 重复上述过程,直到“在一趟排序过程中没有进行过交换记录的操作”为止 六、快速排序 七、归并排序 排序过程 :设初始序列含有n个记录,则可看成n个有序的子序列,每个子序列长度为1 两两合并,得到n/2个长度为2或1的有序子序列 再两两合并,……如此重复,直至得到一个长度为n的有序序列为止 总结: 若待排序记录的个数n较小(<=50)时,可以采用简单排序方法,其中以直接插入排序最简单; 若n较大时,则应采用归并、快速或堆排序,其中归并排序满足稳定性的要求,可以和直接插入排序结合使用,即先利用插入排序得到多个长度小于50的有序子表,然后进行多趟归并。 若待排序记录已按排序码基本有序,应采用直接插入排序或冒泡排序; 以下是上述代码的测试结果:
int[] easilySelectSort(int[] arr) {
int temp, i, j, k, n;
n = arr.length;
temp = arr[0];
for (i = 0; i < n; i++) {
k = i;
for (j = i + 1; j < n; j++) {
if (arr[k] > arr[j]) {
k = j;
temp = arr[i];
arr[i] = arr[k];
arr[k] = temp;
}
}
}
return arr;
}
static int[] heapSort(int[] arr) {
int i, n, temp;
n = arr.length;
//建堆操作,做出一个大顶堆
for (i = n / 2 - 1; i >= 0; i--)
adjust(arr, i, n - 1);
//排序操作,对大顶堆操作
for (i = n - 1; i > 0; i--) {
temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
adjust(arr, 0, i - 1);
}
return arr;
}
//调整函数,负责构建大顶堆,将大的节点往上挪
static void adjust(int[] arr2, int low, int height) {
int i = low, j = i * 2 + 1;//j是i的左节点
int temp = arr2[i];
while (j <= height) {
if (j < height && arr2[j] < arr2[j + 1])
j++;
if (temp < arr2[j]) {
arr2[i] = arr2[j];
i = j;
j = 2 * i + 1;
} else {
break;
}
}
arr2[i] = temp;
}
static int[] bubbleSort(int[] arr) {
int i, j, n, temp;
n = arr.length;
for (i = n - 1; i > 0; i--) {
for (j = 1; j <= i; j++) {
if (arr[j - 1] > arr[j]) {
temp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = temp;
j++;
}
}
}
return arr;
}
static int[] quicklySort(int[] arr, int low, int height) {
int i, j, temp;
i = low;
j = height;
if (low < height) {
temp = arr[low];
while (i < j) {
while (j > i && arr[j] >= temp) j--;
if (j > i) {
arr[i] = arr[j];
i++;
}
while (i < j && arr[i] < temp) i++;
if (i < j) {
arr[j] = arr[i];
j--;
}
}
arr[i] = temp;
quicklySort(arr, low, i - 1);
quicklySort(arr, i + 1, height);
}
return arr;
}
static int[] mergeSort(int[] arr, int low, int height) {
if (low < height) {
int mid = (low + height) / 2;
mergeSort(arr, low, mid);
mergeSort(arr, mid + 1, height);
merge(arr, low, mid, height);
}
return arr;
}
static void merge(int[] arr, int low, int mid, int height) {
int i, j, k;
int n1 = mid - low + 1;
int n2 = height - mid;
int[] L = new int[n1];
int[] R = new int[n2];
for (i = 0; i < n1; i++)
L[i] = arr[low + i];
for (j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
i = 0;
j = 0;
k = low;
while (i < n1 && j < n2) {
if (L[i] < R[j]) {
arr[k] = L[i++];
} else {
arr[k] = R[j++];
}
k++;
}
while (i < n1)
arr[k++] = L[i++];
while (i < n2)
arr[k++] = R[j++];
}
public static void main(String[] args) {
int[] arr = {3, 6, 4, 8, 0, 3, 4, 5, 77, 3, 45, 6, 8, 88, 9, 2435, -765, 0, -9};
System.out.print("排序前的数组: ");
for (int i : arr) {
System.out.print(i + " ");
}
System.out.println();
System.out.print("直接插入排序: ");
int[] arr01 = insertSort(arr);
for (int i : arr01) {
System.out.print(i + " ");
}
System.out.println();
System.out.print("简单选择排序: ");
int[] arr02 = easilySelectSort(arr);
for (int i : arr02) {
System.out.print(i + " ");
}
System.out.println();
System.out.print("冒泡排序: ");
int[] arr03 = bubbleSort(arr);
for (int i : arr03) {
System.out.print(i + " ");
}
System.out.println();
System.out.print("希尔排序: ");
int[] arr04 = shellSort(arr);
for (int i : arr04) {
System.out.print(i + " ");
}
System.out.println();
System.out.print("快速排序: ");
int[] arr05 = quicklySort(arr, 0, arr.length - 1);
for (int i : arr05) {
System.out.print(i + " ");
}
System.out.println();
System.out.print("堆排序: ");
int[] arr06 = heapSort(arr);
for (int i : arr06) {
System.out.print(i + " ");
}
System.out.println();
System.out.print("归并排序: ");
int[] arr07 = mergeSort(arr, 0, arr.length - 1);
for (int i : arr07) {
System.out.print(i + " ");
}
}



