/**
快排的划分
做法
第一步：(初始化)设置两个指针i和j，它们的初值分别为区间的下界和上界，即i=low，i=high；
选取无序区的第一个记录R[i](即R[low])作为基准记录，并将它保存在变量pivot中；
第二步：令j自high起向左扫描，直到找到第1个关键字小于pivot.key的记录R[j]，
将R[j])移至i所指的位置上，这相当于R[j]和基准R[i](即pivot)进行了交换，
使关键字小于基准关键字pivot.key的记录移到了基准的左边，交换后R[j]中相当于是pivot；
然后，令i指针自i+1位置开始向右扫描，直至找到第1个关键字大于pivot.key的记录R[i]，
将R[i]移到i所指的位置上，这相当于交换了R[i]和基准R[j]，使关键字大于基准关键字的记录移到了基准的右边，
交换后R[i]中又相当于存放了pivot；接着令指针j自位置j-1开始向左扫描，如此交替改变扫描方向，
从两端各自往中间靠拢，直至i=j时，i便是基准pivot最终的位置，将pivot放在此位置上就完成了一次划分。
*/
public static int getCurrent(int [] arr, int low, int high)
{
int pivot = arr[low];
while (low < high )
{
while (low<high && arr[high] >= pivot)
{
high--;
}
if (low < high)
{
arr[low++] = arr[high];
}
while (low < high && arr[low] <= pivot)
{
low ++;
}
if (low < high)
{
arr[high--] = arr[low];
}
}
//arr[low] = pivot;
arr[high] = pivot;
return low;
}
/**
完成数组的打印功能
*/
public static void printArray(int [] arr)
{
System.out.print("[");
for(int i=0; i<arr.length; i++)
{
if( i != arr.length-1 )
{
System.out.print(arr[i]+", ");
}
else
{
System.out.println(arr[i]+"]");
}
}
}
}
package com.itheima;
import java.util.Arrays;
/**
* 1、 排序有哪几种方法？请列举。并用JAVA实现一个快速排序.
*
* @author snow
*
*/
public class Test1 {
public static void main(String[] args) {
int arr[] = new int[] { 10, 8, 20, 11, 19 };
// int[] a = {2, 34, 2};// 一个数组的定义和实例化
// System.out.println(Arrays.toString(sort2(arr)));
System.out.println(Arrays.toString(sort4(arr, 0, arr.length - 1)));
System.out.println(Arrays.toString(sort6(arr, arr)));
}
// 冒泡排序法
public static int[] sort1(int[] arr) {
for (int i = 0; i < arr.length; i++) {
int temp = 0;
for (int j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr;
}
// 插入排序法
public static int[] sort2(int[] arr, int left, int right) {
for (int i = left, j = i; i < right; j = ++i) {
int arri = arr[i + 1];
while (arri < arr[j]) {
arr[j + 1] = arr[j];
if (j-- == left) {
break;
}
}
arr[j + 1] = arri;
}
return arr;
}
// 选择排序法
public static int[] sort3(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int j = i;
int temp = 0;
for (int k = i + 1; k < arr.length; k++) {
if (arr[k] < arr[j]) {
j = k;
}
}
if (j != i) {
temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
}
return arr;
}
// 快速排序法
/**
* 快速排序思想： 1，首先找到中间的数，i初始为0递增，直到大于或等于中间的数。j初始为length-1递减，直到小于或者等于中间的数。
* 2，交换i，j所指向的数。
* 3，递归调用该方法。
* @param arr
* @param left
* @param right
* @return
*/
public static int[] sort4(int[] arr, int left, int right) {
int i = left, j = right;
int middle, temp;
middle = arr[(left + right) / 2];
do {
while ((arr[i] < middle) && (i < right)) {
i++;
}
while ((arr[j] > middle) && (j > left)) {
j--;
}
if (i <= j) {
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
} while (i <= j);
if (left < j) {
sort4(arr, left, j);
}
if (right > i)
sort4(arr, i, right);
return arr;
}
public static int[] sort5(int[] arr, int step) {
int min;
int temp;
int sequence = 1;
while (sequence < arr.length / step) {
sequence = sequence * step + 1; // 产生到以step为步长到arr.length的最大值.
}
while (sequence > 0) {
for (int i = sequence; i < arr.length; i++) {
temp = arr[i];
min = i;
while (min > sequence - 1 && arr[min - sequence] > temp) {
arr[min] = arr[min - sequence];
min = min - sequence;
}
arr[min] = temp;
}
sequence = (sequence - 1) / step; // 递减序列关键字
}
return arr;
}
/**
* 归并操作的工作原理如下：
* 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
* 设定两个指针，最初位置分别为两个已经排序序列的起始位置
* 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
* 重复步骤3直到某一指针达到序列尾
* 将另一序列剩下的所有元素直接复制到合并序列尾
* @param data1
* @param data2
* @return
*/
public static int[] sort6(int[] data1, int[] data2) {
int[] temp = new int[data1.length + data2.length];
int i = 0, j = 0, iter = 0;
for (; i < data1.length && j < data2.length;) {
if (data1[i] <= data2[j]) {
temp[iter] = data1[i];
iter++;
i++;
} else {
temp[iter] = data2[j];
iter++;
j++;
}
}
for (; i < data1.length; i++, iter++) {
temp[iter] = data1[i];
}
for (; j < data2.length; j++, iter++) {
temp[iter] = data2[j];
}
return temp;
}
}
|
收藏
淘帖
踩
