常见的排序算法
常见的排序算法有：插入、希尔、选择、冒泡、归并、快速、堆排序。。。
插入排序
算法步骤
一、从数组的第二个数据开始往前比较，如果符合条件（比前面的大或者小，自定义），则让他们交换位置。
二、再用第三个数和第二个比较，符合则交换，但是此处还得继续往前比较。
三、重复步骤二，一直到数据全都排完。
public static void sort(){
int[] ints = new int[]{8, 3, 1, 18, 12, 30};
for (int i = 1; i < ints.length; i++) {
int j = i;
while (j > 0) {
int temp;
if (ints[j] < ints[j - 1]) {
temp = ints[j];
ints[j] = ints[j - 1];
ints[j - 1] = temp;
j--;
} else {
break;
}
}
}
for (int t:ints){
System.err.println(t);
}
}
希尔排序
算法步骤
一、希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序。
二、 随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
public static void sort(){
int[] ints = new int[]{8, 3, 1, 18, 12, 30};
for (int gap = ints.length / 2; gap > 0; gap /= 2) {
for (int i = gap; i < ints.length; i++) {
int j = i;
if (ints[j] < ints[j - gap]) {
int temp = ints[j];
while (j - gap >= 0 && temp < ints[j - gap]){
ints[j] = ints[j - gap];
j-=gap;
}
ints[j] = temp;
}
}
}
for (int a : ints)
System.err.println(a);
}
选择排序
算法步骤
一、首先在未排序的数列中找到最小元素，然后将其存放到数列的起始位置。
二、再从剩余未排序的元素中继续寻找最小元素，然后放到已排序序列的末尾。
三、以此类推，直到所有元素均排序完毕。
public static void sort(){
int[] ints = new int[]{8, 3, 1, 18, 12, 30};
for (int i = 0; i < ints.length; i++) {
int min = ints[i];
for (int j = i+1; j < ints.length; j++) {
if (min > ints[j]) {
int temp = ints[j];
ints[j] = min;
min = temp;
}
}
ints[i] = min;
}
for (int a:ints) {
System.err.println(a);
}
}
冒泡排序
算法步骤
一、比较相邻的元素，如果前一个比后一个大，就交换位置。
二、第一趟排序第1个和第2个一对，比较与交换，随后第2个和第3个一对比较交换，这样直到倒数第2个和最后1个，将最大的数移动到最后一位。
三、第二趟将第二大的数移动至倒数第二位。
四、 重复n-1趟。
public static void sort(){
int[] ints = new int[]{8, 3, 1, 18, 12, 30};
for (int i = 0; i < ints.length; i++) {
for (int j = i+1; j<ints.length; j++) {
if (ints[j] < ints[i]){
int temp = ints[i];
ints[i] = ints[j];
ints[j] = temp;
}
}
}
for (int a:ints) {
System.err.println(a);
}
}
归并排序
算法步骤
一、申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
二、设定两个指针，最初位置分别为两个已经排序序列的起始位置；
三、比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
四、重复步骤三直到某一指针达到序列尾；
五、将另一序列剩下的所有元素直接复制到合并序列尾。
public static int[] sort(int[] ints){
int[] arr = Arrays.copyOf(ints, ints.length);
if (arr.length >= 2) {
int middle = (int) Math.floor(arr.length / 2);
int[] left = Arrays.copyOfRange(arr, 0, middle);
int[] right = Arrays.copyOfRange(arr, middle, arr.length);
return merge(sort(left), sort(right));
}
return arr;
}
private static int[] merge(int[] left, int[] right) {
int[] result = new int[left.length + right.length];
int i = 0;
while (left.length > 0 && right.length > 0) {
if (left[0] <= right[0]) {
result[i++] = left[0];
left = Arrays.copyOfRange(left, 1, left.length);
} else {
result[i++] = right[0];
right = Arrays.copyOfRange(right, 1, right.length);
}
}
while (left.length > 0) {
result[i++] = left[0];
left = Arrays.copyOfRange(left, 1, left.length);
}
while (right.length > 0) {
result[i++] = right[0];
right = Arrays.copyOfRange(right, 1, right.length);
}
return result;
}
快速排序
算法步骤
一、从数列中挑出一个基准值。
二、将所有比基准值小的摆放在基准前面，所有比基准值大的摆在基准的后面(相同的数可以到任一边)；在这个分区退出之后，该基准就处于数列的中间位置。
三、递归地把"基准值前面的子数列"和"基准值后面的子数列"进行排序。
private static void sort(int[] ints, int l, int r) {
if (l < r) {
int i, j, temp;
i = l;
j = r;
temp = ints[i];
while (i < j) {
while (i<j && ints[j] > temp){
j--;
}
if (i<j){
ints[i++] = ints[j];
}
while (i<j && ints[j] < temp) {
i++;
}
if (i< j) {
ints[j--] = ints[i];
}
}
ints[i] =temp;
sort(ints, l, j -1);
sort(ints, i+1, r);
}
}
堆排序
算法步骤
一、将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
二、将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
三、重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。
public static void sort(int []arr){
//1.构建大顶堆
for(int i=arr.length/2-1;i>=0;i--){
//从第一个非叶子结点从下至上，从右至左调整结构
adjustHeap(arr,i,arr.length);
}
//2.调整堆结构+交换堆顶元素与末尾元素
for(int j=arr.length-1;j>0;j--){
swap(arr,0,j);//将堆顶元素与末尾元素进行交换
adjustHeap(arr,0,j);//重新对堆进行调整
}
}
/**
* 调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上）
* @param arr
* @param i
* @param length
*/
public static void adjustHeap(int []arr,int i,int length){
int temp = arr[i];//先取出当前元素i
for(int k=i*2+1;k<length;k=k*2+1){//从i结点的左子结点开始，也就是2i+1处开始
if(k+1<length && arr[k]<arr[k+1]){//如果左子结点小于右子结点，k指向右子结点
k++;
}
if(arr[k] >temp){//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
arr[i] = arr[k];
i = k;
}else{
break;
}
}
arr[i] = temp;//将temp值放到最终的位置
}
/**
* 交换元素
* @param arr
* @param a
* @param b
*/
public static void swap(int []arr,int a ,int b){
int temp=arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
