【数据结构】排序

各种排序方法，直接贴代码

#include "Sort.h"


Sort::Sort(void)
{
}


Sort::~Sort(void)
{

}


void swap(int &a,int &b)
{
	int tmp = a;
	a = b;
	b = tmp;
}

//-------------------------冒泡排序---------------//
//冒泡排序，低效版
void Sort::BubbleSort01(int* array,int len)
{
	int i,j ;
	for (i = 0 ;i < len ;i++)
	{
		for (j = i+1;j<len;j++)
		{
			if (array[i] > array[j])
			{
				swap(array[i],array[j]);
			}
		}
	}
}

//冒泡排序，改进版
void Sort::BubbleSort02(int* array,j;
	for (i = 0 ;i < len ;i++)
	{
		for (j = len - 2; j >= i;j--)
		{
			if (array[j] > array[j+1])
			{
				swap(array[j],array[j+1]);
			}
		}
	}
}

//冒泡排序，优化版
void Sort::BubbleSort03(int* array,j;
	int flag = 1;
	for (i = 0 ;i < len && flag;i++)
	{
		flag = 0;
		for (j = len - 2; j >= i;j--)
		{
			if (array[j] > array[j+1])
			{
				swap(array[j],array[j+1]);
				flag = 1;
			}
		}
	}
}

//-------------------------简单选择排序---------------//
void Sort::SimpleSelectSort(int* array,j,min;
	
	for (i = 0 ; i<len; i++)
	{
		min = i;
		for (j = i+1;j<len;j++)
		{
			if (array[j] < array[min])
			{
				min = j;
			}
		}
		if (min != i)
		{
			swap(array[i],array[min]);
		}
	}
}

//-------------------------直接插入排序---------------//
void Sort::StraightInsertSort(int* array,j ;
	//for (i = 1 ;i<len ;i++)
	//{
	//	for (j = i-1; j>=0 ;j--)
	//	{
	//		if (array[j]>array[j+1])
	//		{
	//			swap(array[j],array[j+1]);
	//		}
	//		else
	//		{
	//			break;
	//		}
	//	}
	//}

	for (i = 1 ;i<len ;i++)
	{
		for (j = i-1; j>=0 && array[j]>array[j+1];j--)
		{
				swap(array[j],array[j+1]);
		}
	}
}

//-------------------------希尔排序---------------//
void Sort::ShellSort(int* array,gap; 
	for (gap = len/2 ;gap>0;gap /=2)
	{
		for (i = gap ;i<len ;i++)
		{
			for (j = i-gap; j>=0 && array[j] > array[j+gap];j -= gap)
			{
					swap(array[j],array[j+gap]);
			}
		}
	}
}

//-------------------------堆排序-----------------//
//增加元素时调整堆
void HeapInsertAdjust(int *HeapAdjust,int len)
{
	int pos = len -1;
	while (pos>0 && HeapAdjust[(pos-1)/2] > HeapAdjust[pos])
	{
			swap(HeapAdjust[(pos-1)/2],HeapAdjust[pos]);
			pos = (pos-1)/2 ;
	}
}

//删除元素时调整堆
void HeapDeleteAdjust(int *HeapAdjust,int len)
{
	int pos = 0;
	while (pos < len-1)
	{
		if (HeapAdjust[pos] > HeapAdjust[2*pos+1] && (2*pos+1) < len)
		{
			swap(HeapAdjust[2*pos+1],HeapAdjust[pos]);
			if (HeapAdjust[pos] > HeapAdjust[2*pos+2] && (2*pos+2) < len)
			{
				swap(HeapAdjust[2*pos+2],HeapAdjust[pos]);
				pos = 2*pos+2;
			}
			else
			{
				pos = 2*pos+1;
			}
		}
		else if (HeapAdjust[pos] > HeapAdjust[2*pos+2] && (2*pos+2) < len)
		{
			swap(HeapAdjust[2*pos+2],HeapAdjust[pos]);
			pos = 2*pos+2;
		}
		else
		{
			break;
		}
	}
}

//往最小堆中插入新数据key
void HeapInsert(int* HeapList,int key,int pos)
{
	HeapList[pos] = key;
	HeapInsertAdjust(HeapList,pos+1);
}

void HeapDelete(int *HeapList,int &len)
{
	swap(HeapList[0],HeapList[len-1]);
	len--;
	HeapDeleteAdjust(HeapList,len);
}
//堆排序
void Sort::HeapSort(int* array,j;
	int * HeapList = (int*)malloc(sizeof(int) * len);
	for (i = 0; i<len; i++)
	{
		HeapInsert(HeapList,array[i],i);
	}
	for (i = 0; i<len; i++)
	{
		printf("%dn",HeapList[i]);
	}
	int heapLen = len;
	for (i = 0;i<len;i++)
	{
		
		printf("---------------n");
		for (j = 0; j<heapLen; j++)
		{
			printf("%d  ",HeapList[j]);
		}
		printf("n");

		array[i] = HeapList[0];
		HeapDelete(HeapList,heapLen);

	}

}

//-------------------------归并排序--------------------//
void mergeArray(int *array,int first,int mid,int end,int* answer)
{
	int i = first,j = mid+1;
	int t = first;
	while (i<=mid && j<=end)
	{
		if (array[i]<=array[j])
		{
			answer[t++] = array[i++];
		}
		else
		{
			answer[t++] = array[j++];
		}
	}
	while (i<=mid)
	{
		answer[t++] = array[i++];

	}
	while (j<=end)
	{
		answer[t++] = array[j++];
	}

	//将answer的值赋给array，不然array不变，没法分治下去
	for (i = first; i < t; i++)
		array[i] = answer[i];
}

void mergeSort(int* array,int start,int* answer)
{
	if (start < end)
	{
		int mid = (end+start)/2 ;
		mergeSort(array,start,mid,answer);
		mergeSort(array,mid+1,end,answer);
		mergeArray(array,answer);
		printf("---------------n");
		for (int j = start; j<=end; j++)
		{
			printf("%d  ",answer[j]);
		}
		printf("n");
	}
}


void Sort::MergeSort(int* array,int len)
{
	int *answer = (int*)malloc(sizeof(int) * len);
	mergeSort(array,len-1,answer);
	//memcpy(array,answer,sizeof(int)*len);
}

//-------------------------快速排序----------------------//
void quickSort(int* array,int end)
{
	if (start >= end)
	{
		return;
	}
	int key = array[start];
	int i = start;
	int j = end;


	while (i < j)
	{

		while (array[j] >= key && i < j)
			j--;
		if (i<j)
			array[i++] = array[j];

		while(array[i] < key && i<j)
			i++;
		if (i<j)
			array[j--] = array[i];
	}
	array[i] = key;

	for (int tt = start; tt<=end; tt++)
	{
		printf("%d  ",array[tt]);
	}
	printf("n");

	quickSort(array,i-1);
	quickSort(array,i+1,end);
}
	
void Sort::QuickSort(int* array,int len)
{
	quickSort(array,len-1);
}

void TEST_Sort()
{
	//int list[] = {9,1,5,8,3,7,4,6,2};
	int list[] = {5,2,9};
	Sort sort;
	//sort.BubbleSort01(list,9);
	//sort.BubbleSort02(list,9);
	//sort.BubbleSort03(list,9);
	//sort.SimpleSelectSort(list,9);
	//sort.StraightInsertSort(list,9);
	//sort.ShellSort(list,9);
	//sort.HeapSort(list,9);
	//sort.MergeSort(list,9);
	sort.QuickSort(list,9);
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!