关于算法:排序算法实现细节

疾速排序采纳分治法。首先从数列中挑出一个元素作为两头值。顺次遍历数据，所有比两头值小的元素放在右边，所有比两头值大的元素放在左边。而后按此办法对左右两个子序列别离进行递归操作，直到所有数据有序。最现实的状况是，每次划分所抉择的两头数恰好将以后序列简直等分（平均排布），整个算法的工夫复杂度为 O(n logn)。最坏的状况是，每次所选的两头数是以后序列中的最大或最小元素（正序和逆序都是最坏），整个排序算法的工夫复杂度为 O(n²)。

均匀工夫复杂度为 O(n logn)，空间复杂度为 O(logn)，是一种不稳固的排序算法。

附算法实现源码：

// 疾速排序
template <class T>
int Partition(T data[],int left,int right)
{T pivot=data[left];
    while(left<right)
    {while(left<right&&data[right]>pivot)
            right--;
        data[left]=data[right];
        while(left<right&&data[left]<=pivot)
            left++;
        data[right]=data[left];
    }
    data[left]=pivot;
    return left;
}
template <class T>
void QuickSort(T data[],int left,int right)
{if(left<right)
{int p=Partition(data,left,right);
    QuickSort(data,left,p-1);
    QuickSort(data,p+1,right);
}
}

遍历所有数据，先在数据中找出最大或最小的元素，放到序列的起始；而后再从余下的数据中持续寻找最大或最小的元素，顺次放到序列中直到所有数据有序。原始数据的排列程序不会影响程序消耗工夫 O(n²)，绝对费时，不适宜大量数据排序。

均匀工夫复杂度为 O(n²)，空间复杂度为 O(1)，是一种不稳固的排序算法。

附算法实现源码：



 
// 抉择排序
template <class T>
void SelectionSort(T data[],int n)
{for(int i=1;i<n;i++)
    {
        int k=i-1;
        for(int j=i;j<n;j++)
        {if(data[j]<data[k])
            {k=j;}
        }
        if(k!=i-1)
        {T t=data[k];
            data[k]=data[i-1];
            data[i-1]=t;
        }
    }
}

将前 i 个（初始为 1）数据假设为有序序列，顺次遍历数据，将以后数据插入到前述有序序列的适当地位，造成前 i + 1 个有序序列，顺次遍历完所有数据，直至序列中所有数据有序。数据是反序时，消耗工夫最长 O(n²)；数据是正序时，消耗工夫最短 O(n)。实用于局部数据曾经排好的大量数据排序。

均匀工夫复杂度为 O(n²)，空间复杂度为 O(1)，是一种稳固的排序算法。

附算法实现源码（直接插入 + 折半插入）：

// 间接插入排序
template <class T>
void InsertionSort(T Data[],int n)
{
    int p,i;
    for(p=1;p<n;p++)
    {T temp=Data[p];
        i=p-1;
        while(i>=0&&Data[i]>temp)
        {Data[i+1]=Data[i];
            i--;
        }
        Data[i+1]=temp;
    }
}



// 折半插入排序
template <class T>
void BinaryInsertionSort(T Data[],int n)
{
    int left,mid,right,p;
    for(p=1;p<n;p++)
    {T temp=Data[p];
        left =0;
        right=n-1;
        while(left<=right)
        {mid=(left+right)/2;
            if(Data[mid]>temp)
                right=mid-1;
            else
                left=mid+1;
        }
        for(int i=p-1;i>=left;i--)
            Data[i+1]=Data[i];
        Data[left]=temp;
    }
}

希尔排序也称递加增量排序，是对插入排序的改良，以就义稳定性的办法提高效率。基本思路是先将整个数据序列宰割成若干子序列别离进行间接插入排序，待整个序列中的记录根本有序时，再对全副数据进行顺次间接插入排序，直至所有数据有序。希尔排序算法的性能与所选取的分组长度序列有很大关系，复杂度下界为 O(n log²n)，在中等规模的数据中体现良好。

均匀工夫复杂度为 O(n^3/2)，空间复杂度为 O(1)，是一种不稳固的排序算法。

附算法实现源码：

// 希尔排序
template <class T>
void ShellSort(T Data[],int n)
{
    int d=n/2;
    while(d>=1)
    {for(int k=0;k<d;k++)
        {for(int i=k+d;i<n;i+=d)
            {T temp=Data[i];
                int j=i-d;
                while(j>=k&&Data[j]>temp)
                {Data[j+d]=Data[j];
                    j-=d;
                }
                Data[j+d]=temp;
            }
        }
        d=d/2;
    }
}

关于算法:排序算法实现细节

一、疾速排序（Quick Sort）

二、抉择排序（Selection Sort）

三、插入排序（Insertion Sort）

四、希尔排序（Shell Sort）