排序算法

#include<stdio.h>
int main()
{
    int i,j,s=0,t,k,n=7,a[7]={9,2,4,6,5,1,8};
    for(i=0;i<n;i++)
    {
        s=0;
        for(j=0;j<n-i-1;j++)
        {
            if(a[j]>a[j+1])//从小到大
            {
                t=a[j];a[j]=a[j+1];a[j+1]=t;s=1;
            }
        }
        if(s==0) break;
    }
    return 0;
}

#include<stdio.h>
int main()
{
    int i,j,s=0,t,k,n=7,a[7]={9,2,4,6,5,1,8};
    for(i=0;i<n-1;i++)
	{
		for(j=i+1,k=i;j<n;j++)
		if(a[j]<a[k]) k=j;//从小到大
		if(k!=i)
		{
			t=a[i];a[i]=a[k];a[k]=t;
		}	
	} 
    for(i=0;i<n;i++)
    {
        printf("%d",a[i]);
    }
    return 0;
}

public class QuickSort {
 2     public static int[] quickSort(int[] arr, int left, int right) {
 3         if (left < right) {
 4             //获取中轴元素所处的位置
 5             int mid = partition(arr, left, right);
 6             //进行分割
 7             arr = quickSort(arr, left, mid - 1);
 8             arr = quickSort(arr, mid + 1, right);
 9         }
10         return arr;
11     }
12 
13     private static int partition(int[] arr, int left, int right) {
14         //选取中轴元素
15         int pivot = arr[left];
16         int i = left + 1;
17         int j = right;
18         while (true) {
19             // 向右找到第一个小于等于 pivot 的元素位置
20             while (i <= j && arr[i] <= pivot) i++;
21             // 向左找到第一个大于等于 pivot 的元素位置
22             while(i <= j && arr[j] >= pivot ) j--;
23             if(i >= j)
24                 break;
25             //交换两个元素的位置，使得左边的元素不大于pivot,右边的不小于pivot
26             int temp = arr[i];
27             arr[i] = arr[j];
28             arr[j] = temp;
29         }
30         arr[left] = arr[j];
31         // 使中轴元素处于有序的位置
32         arr[j] = pivot;
33         return j;
34     }
35 }

public class Head {
 2     // 堆排序
 3     public static int[] headSort(int[] arr) {
 4         int n = arr.length;
 5         //构建大顶堆
 6         for (int i = (n - 2) / 2; i >= 0; i--) {
 7             downAdjust(arr, i, n - 1);
 8         }
 9         //进行堆排序
10         for (int i = n - 1; i >= 1; i--) {
11             // 把堆顶元素与最后一个元素交换
12             int temp = arr[i];
13             arr[i] = arr[0];
14             arr[0] = temp;
15             // 把打乱的堆进行调整，恢复堆的特性
16             downAdjust(arr, 0, i - 1);
17         }
18         return arr;
19     }
20 
21         //下沉操作
22     public static void downAdjust(int[] arr, int parent, int n) {
23         //临时保存要下沉的元素
24         int temp = arr[parent];
25         //定位左孩子节点的位置
26         int child = 2 * parent + 1;
27         //开始下沉
28         while (child <= n) {
29             // 如果右孩子节点比左孩子大，则定位到右孩子
30             if(child + 1 <= n && arr[child] < arr[child + 1])
31                 child++;
32             // 如果孩子节点小于或等于父节点，则下沉结束
33             if (arr[child] <= temp ) break;
34             // 父节点进行下沉
35             arr[parent] = arr[child];
36             parent = child;
37             child = 2 * parent + 1;
38         }
39         arr[parent] = temp;
40     }
41 }

public class BucketSort {
 2     public static int[] BucketSort(int[] arr) {
 3         if(arr == null || arr.length < 2) return arr;
 4 
 5         int n = arr.length;
 6         int max = arr[0];
 7         int min = arr[0];
 8         // 寻找数组的最大值与最小值
 9         for (int i = 1; i < n; i++) {
10             if(min > arr[i])
11                 min = arr[i];
12             if(max < arr[i])
13                 max = arr[i];
14         }
15         //和优化版本的计数排序一样，弄一个大小为 min 的偏移值
16         int d = max - min;
17         //创建 d / 5 + 1 个桶，第 i 桶存放  5*i ~ 5*i+5-1范围的数
18         int bucketNum = d / 5 + 1;
19         ArrayList<LinkedList<Integer>> bucketList = new ArrayList<>(bucketNum);
20         //初始化桶
21         for (int i = 0; i < bucketNum; i++) {
22             bucketList.add(new LinkedList<Integer>());
23         }
24         //遍历原数组，将每个元素放入桶中
25         for (int i = 0; i < n; i++) {
26             bucketList.get((arr[i]-min)/d).add(arr[i] - min);
27         }
28         //对桶内的元素进行排序，我这里采用系统自带的排序工具
29         for (int i = 0; i < bucketNum; i++) {
30             Collections.sort(bucketList.get(i));
31         }
32         //把每个桶排序好的数据进行合并汇总放回原数组
33         int k = 0;
34         for (int i = 0; i < bucketNum; i++) {
35             for (Integer t : bucketList.get(i)) {
36                 arr[k++] = t + min;
37             }
38         }
39         return arr;
40     }
41 }