希尔排序和选择排序

末蓝、 2024-03-24 13:13 16阅读 0赞

#### 排序 ####

*  一.希尔排序
 *  二.选择排序

## 一.希尔排序 ##

> **希尔排序是插入排序的优化版，如果不了解插入排序的可以看看这篇[插入排序][Link 1]。插入排序是一个一个插入，而希尔排序实际上是将数组里的数据先进行预排序，使其接近有序，再逐步减少相隔的个数，直到相隔为0时就排序完成。**

void Sheller(int* a, int n)
    {
        
    	int gap = n;
    	while (gap > 0)
    	{
        
    		gap /= 2;
    		for (int i = gap; i < n; i++)
    		{
        
    			int end = i-gap;
    			int tmp = a[i];
    			while (end >= 0)
    			{
        
    				if (a[end] > tmp)
    				{
        
    					a[end + gap] = a[end];
    					end -= gap;
    				}
    				else
    				{
        
    					break;
    				}
    			}
    			a[end + gap] = tmp;
    		}
    	}
    	for (int i = 0; i < n; i++) printf("%d ", a[i]);
    }
    int main()
    {
        
    	int a[10] = {
         -1,85,14,23,54,13,-3,50,10,12 };
    	Sheller(a,10);
    }

> **希尔排序的时间复杂度大致为n^1.3，约为n\*iogn。**

## 二.选择排序 ##

> **选择排序其实就是依次选出最大和最小的数再将其排在左右两端。**

#include<stdio.h>
    #include<stdlib.h>
    #include<time.h>
    void Swap(int* a, int* b)
    {
        
    	int tmp = *a;
    	*a = *b;
    	*b = tmp;
    }
    void ChooseSort(int* a, int n)
    {
        
    	int right = n - 1;
    	int left = 0;
    	while (right > left)
    	{
        
    		int min = left, max = right;
    		for (int i = left; i <=right; i++)
    		{
        
    			if (a[min] > a[i])
    			{
        
    				min = i;
    				
    			}
    			if (a[max] < a[i])
    			{
        
    				max = i;
    			}
    		}
    		Swap(&a[min], &a[left]);
    		if (left == max)
    		{
        
    			max = min;
    		}
    		Swap(&a[max], &a[right]);
    		left++;
    		right--;
    	}
    	//测试是否有序
    	int st = 0;
    	for (int i = 0; i < n - 1; i++)
    	{
        
    		if (a[i] > a[i + 1])
    		{
        
    			printf("%d->%d,%d\n", a[i],a[i+1],i);
    			st = 1;
    			break;
    		}
    	}
    	if (st)
    	{
        
    		printf("out of order");
    	}
    	else
    	{
        
    		printf("order");
    	}
    }
    
    int main()
    {
        
    	int a[2000];
    	srand((unsigned int)time(NULL));
    	for (int i = 0; i < 2000; i++)
    	{
        
    		a[i] = rand() % 1000;
    	}
    	ChooseSort(a, 2000);
    	return 0;
    }

[Link 1]: http://t.csdn.cn/Gc99F