Sort,排序算法总结

排序算法总结

详细参考链接,寒小阳CSDN

快速排序

介绍：主要就是partition过程。

quickSort(int arr[], int left,int right)  
{
   if(left < right)
   { 
      int mid = partition(arr,left,right);
      quickSort(arr,left,mid-1);
      quickSort(arr,mid+1,right);
   }
}

int partition(int arr[],int left, int right)
{
     if(right <= left)
        return left;
     int key = arr[left];
     while(left < right)
     {
          while(arr[right] > key) right--;
            arr[right] = arr[left];
          while(arr[left] < key) left++
            arr[left] = arr[right];
     }
     arr[left] = key;
     return left;
}

归并排序

介绍：利用二分法，插入排序。

void MSort(arr[], arr_res[],int left,int right)
{
    if(left == right)
	   arr_res[left] = arr[left];
	int mid = (left + right) / 2;
	MSort(arr,arr_res,left,mid);
	MSort(arr,arr_res,mid+1,right);
	Merge(arr,arr_res,left,mid,right);
}

void Merge(int arr[],int arr_res[],int left,int mid,int right)
{
    for(int i = left,k = left,j = mid+1; i <=mid && j<= right;k++)
	{
	   if(arr[i] < arr[j])
	      arr_res[k] = arr[i++];
	   else
	      arr_res[k] = arr[j++];
	}
	if(i < left)
	    arr_res[k...] = arr[i...];
    if(j < right)
	    arr_res[k...] = arr[j...];
    return;
}

简单选择排序

void selectSort(int arr[],int length)
{
    for(int i = 0; i< length - 1 ;i++)
    {
        int minIndex = i;
        for(int j = i+1;j< length;j++)
        {
            if(arr[j] < arr[minIndex])
               j = minIndex;
        }
        if(minIndex != i)
        {
             int temp = arr[i];
             arr[i] = arr[minIndex];
             arr[minIndex] = temp;
        }
    }
}

冒泡排序

void bubbleSort(int arr[],int length)
{
    for(int i = 0; i< length-1;i++)
    {
        for(int j = 1;j < length - i;j++)
        {
           if(arr[j] > arr[j-1])
           {
               int temp = arr[j-1];
               arr[j-1] = arr[j];
               arr[j] = temp;
           }
        }
    }
}