内部排序

蔚落 2022-08-04 09:26 146阅读 0赞

几种内部排序的实现

void SelectSort(int *a,int n)
    {
    	for (int i = 0; i < n - 1; i++)
    	{
    		int flag = -1;
    		for (int j = i + 1; j < n; j++)
    		{
    			if (a[i] > a[j])
    			{
    				flag = j;
    			}
    		}
    		if (flag != -1)
    		{
    			int temp = a[i];
    			a[i] = a[flag];
    			a[flag] = temp;
    		}
    	}
    }
    void InsertSort(int *a, int n)
    {
    	int j;
    	for (int i = 1; i < n; i++)
    	{
    		int temp = a[i];
    		for (j = i-1; j >= 0; j--)
    		{
    			
    			if (temp<a[j])
    			{
    				a[j+1] = a[j];
    			}
    			else
    			{
    				break;
    			}
    		}
    		a[j+1] = temp;
    	}
    }
    void BubbleSort(int *a, int n)
    {
    	for (int i = 0; i < n - 1; i++)
    	{
    		for (int j = 0; j < n - i-1; j++)
    		{
    			if (a[j]>a[j + 1])
    			{
    				int temp = a[j];
    				a[j] = a[j + 1];
    				a[j + 1] = temp;
    			}
    			
    		}
    	}
    }
    void DoubleBubbleSort(int *a, int n)
    {
    	int t = 0;
    	int s = n;
    	while (t < n / 2&&s>n/2)
    	{
    		for (int i = t; i < s-1; i++)
    		{
    			if (a[i]>a[i + 1])
    			{
    				int temp = a[i];
    				a[i] = a[i + 1];
    				a[i + 1] = temp;
    			}
    		}
    		s--;
    		for (int j = s; j > t; j--)
    		{
    			if (a[j] < a[j - 1])
    			{
    				int temp = a[j];
    				a[j] = a[j - 1];
    				a[j - 1] = temp;
    			}
    		}
    		t++;
    	}
    }
    void Merge(int *a, int begin, int mid, int end)
    {
    	int n1 = 0;
    	int n2 = 0;
    	n1 = mid - begin + 1;
    	n2 = end - mid;
    	int *before = new int[n1];
    	int *after = new int[n2];
    	int i = 0;
    	int j = 0;
    	int k = begin;
    	for (i = 0; i < n1; i++)
    	{
    		before[i] = a[k]; 
    		k++;
    	}
    	for (j = 0; j < n2; j++)
    	{
    		after[j] = a[k];
    		k++;
    	}
    	i = 0;
    	j = 0;
    	for (k = begin;i<n1&&j<n2; k++)
    	{
    		if (before[i]>after[j])
    		{
                 a[k] = after[j];
    			 j++;
    		}
    		else
    		{
    			a[k] = before[i];
    			i++;
    		}			
    	}
    	if (i < n1)
    		while (i < n1)
    		{
    		a[k] = before[i];
    		i++;
    		k++;
    		}
    	else
    		while (j < n2)
    		{
    		a[k] = after[j];
    		j++;
    		k++;
    		}
    }
    void MergeSort(int *a, int begin, int end)
    {
    	if (begin < end)
    	{
    		int mid = (begin + end) / 2;
    		MergeSort(a, begin, mid);
    		MergeSort(a, mid + 1, end);
    		Merge(a, begin, mid, end);
    	}
    }
    void QuickSort(int *a, int left,int right)
    {
    	if (left > right)
    		return;
    	int x = a[left];
    	int i = left;
    	int j = right;
    	while (i < j)
    	{
    		while (i<j&&a[j] > x)
    			j--;
    		if (i < j)
    			a[i++] = a[j];
    		while (i<j&&a[i] < x)
    			i++;
    		if (i < j)
    			a[j--] = a[i];
    	}
    	a[i] = x;
    	QuickSort(a,left,i-1);
    	QuickSort(a,i+1, right);
    }
    void ShellSort(int *a, int n)
    {
    	for (int h = n / 2; h > 0; h /= 2)
    	{
    		for (int i = h; i < n; i++)
    		{
    			int temp = a[i];
    			int j;
    			for (j = i - h; j >= 0; j -= h)
    			{
    				if (a[j]>a[i])
    					a[j + h] = a[j];
    				else
    					break;
    			}
    			a[j + h] = temp;
    		}
    	}
    }
    void Heapfy(int A[], int idx, int max)      //建立最大堆  
    {
    	int left = idx * 2 + 1;
    	int right = left + 1;
    
    	int largest = idx;
    
    	if (left<max&&A[left]>A[idx]){ largest = left; }
    
    	if (right<max&&A[largest]<A[right]){ largest = right; }
    
    	if (largest != idx)
    	{
    		int temp = A[largest];
    		A[largest] = A[idx];
    		A[idx] = temp;
    		Heapfy(A, largest, max);
    
    	}
    }
    
    void HeapSort(int A[], int ll)
    {
    	int len = ll;
    	for (int i = len / 2 - 1; i >= 0; --i)
    	{
    		Heapfy(A, i, len);
    	}
    	for (int i = len - 1; i >= 1; --i)
    	{
    		int temp = A[0];  
    		A[0] = A[i];
    		A[i] = temp;
    		Heapfy(A, 0, i);
    	}
    }
    int main()
    {
    	int a[] = { 3, 2, 5, 1, 3, 7, 6, 8 };
    	int n = sizeof(a) / sizeof(a[0]);
    	//DoubleBubbleSort(a, n);
    	//MergeSort(a, 0, n-1);
    	//QuickSort(a, 0, n - 1);
    	//ShellSort(a, n);
    	HeapSort(a, n);
    	for (int i = 0; i < n; i++)
    	{
    		cout << a[i] << '\t';
    	}
    	getchar();
    }